{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "本文介绍Python数据结构与算法，原文在[Problem Solving with Algorithms and Data Structures](http://interactivepython.org/runestone/static/pythonds/index.html)\n",
    "\n",
    "<!-- TEASER_END -->"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from IPython.display import HTML"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<table border=\"0\" class=\"table\" id=\"tbl-fntable\">\n",
    "<caption><strong>Table 1: Common Functions for Big-O</strong></caption>\n",
    "<colgroup>\n",
    "<col width=\"50%\">\n",
    "<col width=\"50%\">\n",
    "</colgroup>\n",
    "<thead valign=\"bottom\">\n",
    "<tr class=\"row-odd\"><th class=\"head\"><strong>f(n)</strong></th>\n",
    "<th class=\"head\"><strong>Name</strong></th>\n",
    "</tr>\n",
    "</thead>\n",
    "<tbody valign=\"top\">\n",
    "<tr class=\"row-even\"><td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-23-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-181\" style=\"width: 0.647em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 0.53em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.876em 1000.003em 2.872em -0.465em); top: -2.69em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-182\"><span class=\"mn\" id=\"MathJax-Span-183\" style=\"font-family: MathJax_Main;\">1</span></span><span style=\"display: inline-block; width: 0px; height: 2.696em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.932em; vertical-align: -0.068em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-23\">1</script></span></td>\n",
    "<td>Constant</td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-24-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-184\" style=\"width: 2.52em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 2.052em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.818em 1000.003em 3.106em -0.524em); top: -2.69em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-185\"><span class=\"mi\" id=\"MathJax-Span-186\" style=\"font-family: MathJax_Main;\">log</span><span class=\"mo\" id=\"MathJax-Span-187\"></span><span class=\"mi\" id=\"MathJax-Span-188\" style=\"font-family: MathJax_Math; font-style: italic; padding-left: 0.179em;\">n</span></span><span style=\"display: inline-block; width: 0px; height: 2.696em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.218em; vertical-align: -0.354em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-24\">\\log n</script></span></td>\n",
    "<td>Logarithmic</td>\n",
    "</tr>\n",
    "<tr class=\"row-even\"><td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-25-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-189\" style=\"width: 0.823em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 0.647em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.818em 1000.003em 2.638em -0.524em); top: -2.456em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-190\"><span class=\"mi\" id=\"MathJax-Span-191\" style=\"font-family: MathJax_Math; font-style: italic;\">n</span></span><span style=\"display: inline-block; width: 0px; height: 2.462em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.718em; vertical-align: -0.068em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-25\">n</script></span></td>\n",
    "<td>Linear</td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-26-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-192\" style=\"width: 3.457em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 2.813em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.818em 1000.003em 3.106em -0.524em); top: -2.69em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-193\"><span class=\"mi\" id=\"MathJax-Span-194\" style=\"font-family: MathJax_Math; font-style: italic;\">n</span><span class=\"mi\" id=\"MathJax-Span-195\" style=\"font-family: MathJax_Main; padding-left: 0.179em;\">log</span><span class=\"mo\" id=\"MathJax-Span-196\"></span><span class=\"mi\" id=\"MathJax-Span-197\" style=\"font-family: MathJax_Math; font-style: italic; padding-left: 0.179em;\">n</span></span><span style=\"display: inline-block; width: 0px; height: 2.696em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.218em; vertical-align: -0.354em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-26\">n\\log n</script></span></td>\n",
    "<td>Log Linear</td>\n",
    "</tr>\n",
    "<tr class=\"row-even\"><td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-27-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-198\" style=\"width: 1.35em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 1.115em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.115em 1000.003em 2.286em -0.524em); top: -2.105em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-199\"><span class=\"msubsup\" id=\"MathJax-Span-200\"><span style=\"display: inline-block; position: relative; width: 1.115em; height: 0px;\"><span style=\"position: absolute; clip: rect(1.818em 1000.003em 2.638em -0.524em); top: -2.456em; left: 0.003em;\"><span class=\"mi\" id=\"MathJax-Span-201\" style=\"font-family: MathJax_Math; font-style: italic;\">n</span><span style=\"display: inline-block; width: 0px; height: 2.462em;\"></span></span><span style=\"position: absolute; top: -2.632em; left: 0.647em;\"><span class=\"texatom\" id=\"MathJax-Span-202\"><span class=\"mrow\" id=\"MathJax-Span-203\"><span class=\"mn\" id=\"MathJax-Span-204\" style=\"font-size: 70.7%; font-family: MathJax_Main;\">2</span></span></span><span style=\"display: inline-block; width: 0px; height: 2.286em;\"></span></span></span></span></span><span style=\"display: inline-block; width: 0px; height: 2.111em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.146em; vertical-align: -0.068em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-27\">n^{2}</script></span></td>\n",
    "<td>Quadratic</td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-28-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-205\" style=\"width: 1.35em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 1.115em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.115em 1000.003em 2.286em -0.524em); top: -2.105em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-206\"><span class=\"msubsup\" id=\"MathJax-Span-207\"><span style=\"display: inline-block; position: relative; width: 1.115em; height: 0px;\"><span style=\"position: absolute; clip: rect(1.818em 1000.003em 2.638em -0.524em); top: -2.456em; left: 0.003em;\"><span class=\"mi\" id=\"MathJax-Span-208\" style=\"font-family: MathJax_Math; font-style: italic;\">n</span><span style=\"display: inline-block; width: 0px; height: 2.462em;\"></span></span><span style=\"position: absolute; top: -2.632em; left: 0.647em;\"><span class=\"texatom\" id=\"MathJax-Span-209\"><span class=\"mrow\" id=\"MathJax-Span-210\"><span class=\"mn\" id=\"MathJax-Span-211\" style=\"font-size: 70.7%; font-family: MathJax_Main;\">3</span></span></span><span style=\"display: inline-block; width: 0px; height: 2.286em;\"></span></span></span></span></span><span style=\"display: inline-block; width: 0px; height: 2.111em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.146em; vertical-align: -0.068em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-28\">n^{3}</script></span></td>\n",
    "<td>Cubic</td>\n",
    "</tr>\n",
    "<tr class=\"row-even\"><td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-29-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-212\" style=\"width: 1.232em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 0.998em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.232em 1000.003em 2.286em -0.465em); top: -2.105em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-213\"><span class=\"msubsup\" id=\"MathJax-Span-214\"><span style=\"display: inline-block; position: relative; width: 0.998em; height: 0px;\"><span style=\"position: absolute; clip: rect(1.876em 1000.003em 2.872em -0.465em); top: -2.69em; left: 0.003em;\"><span class=\"mn\" id=\"MathJax-Span-215\" style=\"font-family: MathJax_Main;\">2</span><span style=\"display: inline-block; width: 0px; height: 2.696em;\"></span></span><span style=\"position: absolute; top: -2.632em; left: 0.53em;\"><span class=\"texatom\" id=\"MathJax-Span-216\"><span class=\"mrow\" id=\"MathJax-Span-217\"><span class=\"mi\" id=\"MathJax-Span-218\" style=\"font-size: 70.7%; font-family: MathJax_Math; font-style: italic;\">n</span></span></span><span style=\"display: inline-block; width: 0px; height: 2.228em;\"></span></span></span></span></span><span style=\"display: inline-block; width: 0px; height: 2.111em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.004em; vertical-align: -0.068em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-29\">2^{n}</script></span></td>\n",
    "<td>Exponential</td>\n",
    "</tr>\n",
    "</tbody>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<table border=\"0\" class=\"table\" id=\"tbl-listbigo\">\n",
    "<caption><strong>Table 2: Big-O Efficiency of Python List Operators</strong></caption>\n",
    "<colgroup>\n",
    "<col width=\"50%\">\n",
    "<col width=\"50%\">\n",
    "</colgroup>\n",
    "<thead valign=\"bottom\">\n",
    "<tr class=\"row-odd\"><th class=\"head\">Operation</th>\n",
    "<th class=\"head\">Big-O Efficiency</th>\n",
    "</tr>\n",
    "</thead>\n",
    "<tbody valign=\"top\">\n",
    "<tr class=\"row-even\"><td>index []</td>\n",
    "<td>O(1)</td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td>index assignment</td>\n",
    "<td>O(1)</td>\n",
    "</tr>\n",
    "<tr class=\"row-even\"><td>append</td>\n",
    "<td>O(1)</td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td>pop()</td>\n",
    "<td>O(1)</td>\n",
    "</tr>\n",
    "<tr class=\"row-even\"><td>pop(i)</td>\n",
    "<td>O(n)</td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td>insert(i,item)</td>\n",
    "<td>O(n)</td>\n",
    "</tr>\n",
    "<tr class=\"row-even\"><td>del operator</td>\n",
    "<td>O(n)</td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td>iteration</td>\n",
    "<td>O(n)</td>\n",
    "</tr>\n",
    "<tr class=\"row-even\"><td>contains (in)</td>\n",
    "<td>O(n)</td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td>get slice [x:y]</td>\n",
    "<td>O(k)</td>\n",
    "</tr>\n",
    "<tr class=\"row-even\"><td>del slice</td>\n",
    "<td>O(n)</td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td>set slice</td>\n",
    "<td>O(n+k)</td>\n",
    "</tr>\n",
    "<tr class=\"row-even\"><td>reverse</td>\n",
    "<td>O(n)</td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td>concatenate</td>\n",
    "<td>O(k)</td>\n",
    "</tr>\n",
    "<tr class=\"row-even\"><td>sort</td>\n",
    "<td>O(n log n)</td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td>multiply</td>\n",
    "<td>O(nk)</td>\n",
    "</tr>\n",
    "</tbody>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<table border=\"0\" class=\"table\" id=\"tbl-dictbigo\">\n",
    "<caption><strong>Table 3: Big-O Efficiency of Python Dictionary Operations</strong></caption>\n",
    "<colgroup>\n",
    "<col width=\"50%\">\n",
    "<col width=\"50%\">\n",
    "</colgroup>\n",
    "<thead valign=\"bottom\">\n",
    "<tr class=\"row-odd\"><th class=\"head\">operation</th>\n",
    "<th class=\"head\">Big-O Efficiency</th>\n",
    "</tr>\n",
    "</thead>\n",
    "<tbody valign=\"top\">\n",
    "<tr class=\"row-even\"><td>copy</td>\n",
    "<td>O(n)</td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td>get item</td>\n",
    "<td>O(1)</td>\n",
    "</tr>\n",
    "<tr class=\"row-even\"><td>set item</td>\n",
    "<td>O(1)</td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td>delete item</td>\n",
    "<td>O(1)</td>\n",
    "</tr>\n",
    "<tr class=\"row-even\"><td>contains (in)</td>\n",
    "<td>O(1)</td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td>iteration</td>\n",
    "<td>O(n)</td>\n",
    "</tr>\n",
    "</tbody>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Stack Abstract Data Type"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<table border=\"0\" class=\"table\" id=\"tbl-stackops\">\n",
    "<caption><strong>Table 1: Sample Stack Operations</strong></caption>\n",
    "<colgroup>\n",
    "<col width=\"40%\">\n",
    "<col width=\"34%\">\n",
    "<col width=\"26%\">\n",
    "</colgroup>\n",
    "<thead valign=\"bottom\">\n",
    "<tr class=\"row-odd\"><th class=\"head\"><strong>Stack Operation</strong></th>\n",
    "<th class=\"head\"><strong>Stack Contents</strong></th>\n",
    "<th class=\"head\"><strong>Return Value</strong></th>\n",
    "</tr>\n",
    "</thead>\n",
    "<tbody valign=\"top\">\n",
    "<tr class=\"row-even\"><td><code>s.isEmpty()</code></td>\n",
    "<td><code>[]</code></td>\n",
    "<td><code>True</code></td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td><code>s.push(4)</code></td>\n",
    "<td><code>[4]</code></td>\n",
    "<td>&nbsp;</td>\n",
    "</tr>\n",
    "<tr class=\"row-even\"><td><code>s.push('dog')</code></td>\n",
    "<td><code>[4,'dog']</code></td>\n",
    "<td>&nbsp;</td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td><code>s.peek()</code></td>\n",
    "<td><code>[4,'dog']</code></td>\n",
    "<td><code>'dog'</code></td>\n",
    "</tr>\n",
    "<tr class=\"row-even\"><td><code>s.push(True)</code></td>\n",
    "<td><code>[4,'dog',True]</code></td>\n",
    "<td>&nbsp;</td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td><code>s.size()</code></td>\n",
    "<td><code>[4,'dog',True]</code></td>\n",
    "<td><code>3</code></td>\n",
    "</tr>\n",
    "<tr class=\"row-even\"><td><code>s.isEmpty()</code></td>\n",
    "<td><code>[4,'dog',True]</code></td>\n",
    "<td><code>False</code></td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td><code>s.push(8.4)</code></td>\n",
    "<td><code>[4,'dog',True,8.4]</code></td>\n",
    "<td>&nbsp;</td>\n",
    "</tr>\n",
    "<tr class=\"row-even\"><td><code>s.pop()</code></td>\n",
    "<td><code>[4,'dog',True]</code></td>\n",
    "<td><code>8.4</code></td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td><code>s.pop()</code></td>\n",
    "<td><code>[4,'dog']</code></td>\n",
    "<td><code>True</code></td>\n",
    "</tr>\n",
    "<tr class=\"row-even\"><td><code>s.size()</code></td>\n",
    "<td><code>[4,'dog']</code></td>\n",
    "<td><code>2</code></td>\n",
    "</tr>\n",
    "</tbody>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementing a Stack in Python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Stack:\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "\n",
    "    def isEmpty(self):\n",
    "        return self.items == []\n",
    "\n",
    "    def push(self, item):\n",
    "        self.items.append(item)\n",
    "\n",
    "    def pop(self):\n",
    "        return self.items.pop()\n",
    "\n",
    "    def peek(self):\n",
    "        return self.items[len(self.items)-1]\n",
    "\n",
    "    def size(self):\n",
    "        return len(self.items)\n",
    "    \n",
    "    def show(self):\n",
    "        return [self.pop() for x in range(self.size())]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'elppa'"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def revstring(mystr):\n",
    "    # your code here\n",
    "    t = Stack()\n",
    "    [t.push(x) for x in mystr]\n",
    "    return ''.join(t.show())\n",
    "\n",
    "revstring('apple')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Simple Balanced Parentheses"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "from pythonds.basic.stack import Stack\n",
    "\n",
    "def parChecker(symbolString):\n",
    "    s = Stack()\n",
    "    balanced = True\n",
    "    index = 0\n",
    "    while index < len(symbolString) and balanced:\n",
    "        symbol = symbolString[index]\n",
    "        if symbol == \"(\":\n",
    "            s.push(symbol)\n",
    "        else:\n",
    "            if s.isEmpty():\n",
    "                balanced = False\n",
    "            else:\n",
    "                s.pop()\n",
    "\n",
    "        index = index + 1\n",
    "\n",
    "    if balanced and s.isEmpty():\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "print(parChecker('((()))'))\n",
    "print(parChecker('(()'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Balanced Symbols (A General Case)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "from pythonds.basic.stack import Stack\n",
    "\n",
    "def parChecker(symbolString):\n",
    "    s = Stack()\n",
    "    balanced = True\n",
    "    index = 0\n",
    "    while index < len(symbolString) and balanced:\n",
    "        symbol = symbolString[index]\n",
    "        if symbol in \"([{\":\n",
    "            s.push(symbol)\n",
    "        else:\n",
    "            if s.isEmpty():\n",
    "                balanced = False\n",
    "            else:\n",
    "                top = s.pop()\n",
    "                if not matches(top,symbol):\n",
    "                       balanced = False\n",
    "        index = index + 1\n",
    "    if balanced and s.isEmpty():\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "def matches(open,close):\n",
    "    opens = \"([{\"\n",
    "    closers = \")]}\"\n",
    "    return opens.index(open) == closers.index(close)\n",
    "\n",
    "\n",
    "print(parChecker('{{([][])}()}'))\n",
    "print(parChecker('[{()]'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Converting Decimal Numbers to Binary Numbers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "11001\n",
      "19\n"
     ]
    }
   ],
   "source": [
    "from pythonds.basic.stack import Stack\n",
    "\n",
    "def baseConverter(decNumber,base):\n",
    "    digits = \"0123456789ABCDEF\"\n",
    "\n",
    "    remstack = Stack()\n",
    "\n",
    "    while decNumber > 0:\n",
    "        rem = decNumber % base\n",
    "        remstack.push(rem)\n",
    "        decNumber = decNumber // base\n",
    "\n",
    "    newString = \"\"\n",
    "    while not remstack.isEmpty():\n",
    "        newString = newString + digits[remstack.pop()]\n",
    "\n",
    "    return newString\n",
    "\n",
    "print(baseConverter(25,2))\n",
    "print(baseConverter(25,16))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Infix, Prefix and Postfix Expressions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Create an empty stack called opstack for keeping operators. Create an empty list for output.\n",
    "2. Convert the input infix string to a list by using the string method split.\n",
    "3. Scan the token list from left to right.\n",
    "    - If the token is an operand, append it to the end of the output list.\n",
    "    - If the token is a left parenthesis, push it on the opstack.\n",
    "    - If the token is a right parenthesis, pop the opstack until the corresponding left parenthesis is removed. Append each operator to the end of the output list.\n",
    "    - If the token is an operator, *, /, +, or -, push it on the opstack. However, first remove any operators already on the opstack that have higher or equal precedence and append them to the output list.\n",
    "4. When the input expression has been completely processed, check the opstack. Any operators still on the stack can be removed and appended to the end of the output list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A B * C D * +\n",
      "A B + C * D E - F G + * -\n"
     ]
    }
   ],
   "source": [
    "from pythonds.basic.stack import Stack\n",
    "\n",
    "def infixToPostfix(infixexpr):\n",
    "    prec = {}\n",
    "    prec[\"*\"] = 3\n",
    "    prec[\"/\"] = 3\n",
    "    prec[\"+\"] = 2\n",
    "    prec[\"-\"] = 2\n",
    "    prec[\"(\"] = 1\n",
    "    opStack = Stack()\n",
    "    postfixList = []\n",
    "    tokenList = infixexpr.split()\n",
    "\n",
    "    for token in tokenList:\n",
    "        if token in \"ABCDEFGHIJKLMNOPQRSTUVWXYZ\" or token in \"0123456789\":\n",
    "            postfixList.append(token)\n",
    "        elif token == '(':\n",
    "            opStack.push(token)\n",
    "        elif token == ')':\n",
    "            topToken = opStack.pop()\n",
    "            while topToken != '(':\n",
    "                postfixList.append(topToken)\n",
    "                topToken = opStack.pop()\n",
    "        else:\n",
    "            while (not opStack.isEmpty()) and \\\n",
    "               (prec[opStack.peek()] >= prec[token]):\n",
    "                  postfixList.append(opStack.pop())\n",
    "            opStack.push(token)\n",
    "\n",
    "    while not opStack.isEmpty():\n",
    "        postfixList.append(opStack.pop())\n",
    "    return \" \".join(postfixList)\n",
    "\n",
    "print(infixToPostfix(\"A * B + C * D\"))\n",
    "print(infixToPostfix(\"( A + B ) * C - ( D - E ) * ( F + G )\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Postfix Evaluation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Create an empty stack called operandStack.\n",
    "2. Convert the string to a list by using the string method split.\n",
    "3. Scan the token list from left to right.\n",
    "    - If the token is an operand, convert it from a string to an integer and push the value onto the operandStack.\n",
    "    - If the token is an operator, *, /, +, or -, it will need two operands. Pop the operandStack twice. The first pop is the second operand and the second pop is the first operand. Perform the arithmetic operation. Push the result back on the operandStack.\n",
    "4. When the input expression has been completely processed, the result is on the stack. Pop the operandStack and return the value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.0\n"
     ]
    }
   ],
   "source": [
    "from pythonds.basic.stack import Stack\n",
    "\n",
    "def postfixEval(postfixExpr):\n",
    "    operandStack = Stack()\n",
    "    tokenList = postfixExpr.split()\n",
    "\n",
    "    for token in tokenList:\n",
    "        if token in \"0123456789\":\n",
    "            operandStack.push(int(token))\n",
    "        else:\n",
    "            operand2 = operandStack.pop()\n",
    "            operand1 = operandStack.pop()\n",
    "            result = doMath(token,operand1,operand2)\n",
    "            operandStack.push(result)\n",
    "    return operandStack.pop()\n",
    "\n",
    "def doMath(op, op1, op2):\n",
    "    if op == \"*\":\n",
    "        return op1 * op2\n",
    "    elif op == \"/\":\n",
    "        return op1 / op2\n",
    "    elif op == \"+\":\n",
    "        return op1 + op2\n",
    "    else:\n",
    "        return op1 - op2\n",
    "\n",
    "print(postfixEval('7 8 + 3 2 + /'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Queue Abstract Data Type"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<table border=\"0\" class=\"table\" id=\"tbl-queueoperations\">\n",
    "<caption><strong>Table 1: Example Queue Operations</strong></caption>\n",
    "<colgroup>\n",
    "<col width=\"40%\">\n",
    "<col width=\"34%\">\n",
    "<col width=\"26%\">\n",
    "</colgroup>\n",
    "<thead valign=\"bottom\">\n",
    "<tr class=\"row-odd\"><th class=\"head\"><strong>Queue Operation</strong></th>\n",
    "<th class=\"head\"><strong>Queue Contents</strong></th>\n",
    "<th class=\"head\"><strong>Return Value</strong></th>\n",
    "</tr>\n",
    "</thead>\n",
    "<tbody valign=\"top\">\n",
    "<tr class=\"row-even\"><td><code>q.isEmpty()</code></td>\n",
    "<td><code>[]</code></td>\n",
    "<td><code>True</code></td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td><code>q.enqueue(4)</code></td>\n",
    "<td><code>[4]</code></td>\n",
    "<td>&nbsp;</td>\n",
    "</tr>\n",
    "<tr class=\"row-even\"><td><code>q.enqueue('dog')</code></td>\n",
    "<td><code>['dog',4]</code></td>\n",
    "<td>&nbsp;</td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td><code>q.enqueue(True)</code></td>\n",
    "<td><code>[True,'dog',4]</code></td>\n",
    "<td>&nbsp;</td>\n",
    "</tr>\n",
    "<tr class=\"row-even\"><td><code>q.size()</code></td>\n",
    "<td><code>[True,'dog',4]</code></td>\n",
    "<td><code>3</code></td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td><code>q.isEmpty()</code></td>\n",
    "<td><code>[True,'dog',4]</code></td>\n",
    "<td><code>False</code></td>\n",
    "</tr>\n",
    "<tr class=\"row-even\"><td><code>q.enqueue(8.4)</code></td>\n",
    "<td><code>[8.4,True,'dog',4]</code></td>\n",
    "<td>&nbsp;</td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td><code>q.dequeue()</code></td>\n",
    "<td><code>[8.4,True,'dog']</code></td>\n",
    "<td><code>4</code></td>\n",
    "</tr>\n",
    "<tr class=\"row-even\"><td><code>q.dequeue()</code></td>\n",
    "<td><code>[8.4,True]</code></td>\n",
    "<td><code>'dog'</code></td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td><code>q.size()</code></td>\n",
    "<td><code>[8.4,True]</code></td>\n",
    "<td><code>2</code></td>\n",
    "</tr>\n",
    "</tbody>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementing a Queue in Python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Queue:\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "\n",
    "    def isEmpty(self):\n",
    "        return self.items == []\n",
    "\n",
    "    def enqueue(self, item):\n",
    "        self.items.insert(0,item)\n",
    "\n",
    "    def dequeue(self):\n",
    "        return self.items.pop()\n",
    "\n",
    "    def size(self):\n",
    "        return len(self.items)\n",
    "    \n",
    "    def show(self):\n",
    "        return map(lambda x: self.dequeue(), range(self.size()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<map at 0x7f83a45b56d8>"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q = Queue()\n",
    "q.enqueue('hello')\n",
    "q.enqueue('dog')\n",
    "q.enqueue(3)\n",
    "q.dequeue()\n",
    "q.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Simulation: Hot Potato"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Susan\n"
     ]
    }
   ],
   "source": [
    "from pythonds.basic.queue import Queue\n",
    "\n",
    "def hotPotato(namelist, num):\n",
    "    simqueue = Queue()\n",
    "    for name in namelist:\n",
    "        simqueue.enqueue(name)\n",
    "    \n",
    "    while simqueue.size() > 1:\n",
    "        for i in range(num):\n",
    "            simqueue.enqueue(simqueue.dequeue())\n",
    "        simqueue.dequeue()\n",
    "    return simqueue.dequeue()\n",
    "\n",
    "print(hotPotato([\"Bill\",\"David\",\"Susan\",\"Jane\",\"Kent\",\"Brad\"],7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<iframe width=\"800\" height=\"500\" frameborder=\"0\" src=\"http://pythontutor.com/iframe-embed.html#code=class+Queue%3A%0A++++def+__init__(self)%3A%0A++++++++self.items+%3D+%5B%5D%0A%0A++++def+isEmpty(self)%3A%0A++++++++return+self.items+%3D%3D+%5B%5D%0A%0A++++def+enqueue(self,+item)%3A%0A++++++++self.items.insert(0,item)%0A%0A++++def+dequeue(self)%3A%0A++++++++return+self.items.pop()%0A%0A++++def+size(self)%3A%0A++++++++return+len(self.items)%0A++++%0A++++def+show(self)%3A%0A++++++++return+map(lambda+x%3A+self.dequeue(),+range(self.size()))%0A%0Adef+hotPotato(namelist,+num)%3A%0A++++simqueue+%3D+Queue()%0A++++for+name+in+namelist%3A%0A++++++++simqueue.enqueue(name)%0A%0A++++while+simqueue.size()+%3E+1%3A%0A++++++++for+i+in+range(num)%3A%0A++++++++++++simqueue.enqueue(simqueue.dequeue())%0A%0A++++++++simqueue.dequeue()%0A%0A++++return+simqueue.dequeue()%0A%0Aprint(hotPotato(%5B%22Bill%22,%22David%22,%22Susan%22,%22Jane%22,%22Kent%22,%22Brad%22%5D,7))%0A&origin=opt-frontend.js&cumulative=false&heapPrimitives=false&drawParentPointers=false&textReferences=false&showOnlyOutputs=false&py=2&rawInputLstJSON=%5B%5D&curInstr=0&codeDivWidth=350&codeDivHeight=400\"> </iframe>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML at 0x7f83a45b2240>"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "HTML('<iframe width=\"800\" height=\"500\" frameborder=\"0\" src=\"http://pythontutor.com/iframe-embed.html#code=class+Queue%3A%0A++++def+__init__(self)%3A%0A++++++++self.items+%3D+%5B%5D%0A%0A++++def+isEmpty(self)%3A%0A++++++++return+self.items+%3D%3D+%5B%5D%0A%0A++++def+enqueue(self,+item)%3A%0A++++++++self.items.insert(0,item)%0A%0A++++def+dequeue(self)%3A%0A++++++++return+self.items.pop()%0A%0A++++def+size(self)%3A%0A++++++++return+len(self.items)%0A++++%0A++++def+show(self)%3A%0A++++++++return+map(lambda+x%3A+self.dequeue(),+range(self.size()))%0A%0Adef+hotPotato(namelist,+num)%3A%0A++++simqueue+%3D+Queue()%0A++++for+name+in+namelist%3A%0A++++++++simqueue.enqueue(name)%0A%0A++++while+simqueue.size()+%3E+1%3A%0A++++++++for+i+in+range(num)%3A%0A++++++++++++simqueue.enqueue(simqueue.dequeue())%0A%0A++++++++simqueue.dequeue()%0A%0A++++return+simqueue.dequeue()%0A%0Aprint(hotPotato(%5B%22Bill%22,%22David%22,%22Susan%22,%22Jane%22,%22Kent%22,%22Brad%22%5D,7))%0A&origin=opt-frontend.js&cumulative=false&heapPrimitives=false&drawParentPointers=false&textReferences=false&showOnlyOutputs=false&py=2&rawInputLstJSON=%5B%5D&curInstr=0&codeDivWidth=350&codeDivHeight=400\"> </iframe>')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Simulation: Printing Tasks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Create a queue of print tasks. Each task will be given a timestamp upon its arrival. The queue is empty to start.\n",
    "2. For each second (currentSecond):\n",
    "    - Does a new print task get created? If so, add it to the queue with the currentSecond as the timestamp.\n",
    "    - If the printer is not busy and if a task is waiting,\n",
    "        - Remove the next task from the print queue and assign it to the printer.\n",
    "        - Subtract the timestamp from the currentSecond to compute the waiting time for that task.\n",
    "        - Append the waiting time for that task to a list for later processing.\n",
    "        - Based on the number of pages in the print task, figure out how much time will be required.\n",
    "    - The printer now does one second of printing if necessary. It also subtracts one second from the time required for that task.\n",
    "    - If the task has been completed, in other words the time required has reached zero, the printer is no longer busy.\n",
    "3. After the simulation is complete, compute the average waiting time from the list of waiting times generated."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Average Wait  31.79 secs   0 tasks remaining.\n",
      "Average Wait  63.80 secs   0 tasks remaining.\n",
      "Average Wait  29.67 secs   0 tasks remaining.\n",
      "Average Wait 161.00 secs   0 tasks remaining.\n",
      "Average Wait 903.00 secs  11 tasks remaining.\n",
      "Average Wait 338.50 secs   2 tasks remaining.\n",
      "Average Wait  82.90 secs   0 tasks remaining.\n",
      "Average Wait 164.33 secs   1 tasks remaining.\n",
      "Average Wait  98.30 secs   1 tasks remaining.\n",
      "Average Wait  50.20 secs   1 tasks remaining.\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "class Printer:\n",
    "    def __init__(self, ppm):\n",
    "        self.pagerate = ppm\n",
    "        self.currentTask = None\n",
    "        self.timeRemaining = 0\n",
    "\n",
    "    def tick(self):\n",
    "        if self.currentTask != None:\n",
    "            self.timeRemaining = self.timeRemaining - 1\n",
    "            if self.timeRemaining <= 0:\n",
    "                self.currentTask = None\n",
    "\n",
    "    def busy(self):\n",
    "        if self.currentTask != None:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    def startNext(self,newtask):\n",
    "        self.currentTask = newtask\n",
    "        self.timeRemaining = newtask.getPages() * 60/self.pagerate\n",
    "\n",
    "class Task:\n",
    "    def __init__(self,time):\n",
    "        self.timestamp = time\n",
    "        self.pages = random.randrange(1,21)\n",
    "\n",
    "    def getStamp(self):\n",
    "        return self.timestamp\n",
    "\n",
    "    def getPages(self):\n",
    "        return self.pages\n",
    "\n",
    "    def waitTime(self, currenttime):\n",
    "        return currenttime - self.timestamp\n",
    "\n",
    "\n",
    "def simulation(numSeconds, pagesPerMinute):\n",
    "\n",
    "    labprinter = Printer(pagesPerMinute)\n",
    "    printQueue = Queue()\n",
    "    waitingtimes = []\n",
    "\n",
    "    for currentSecond in range(numSeconds):\n",
    "\n",
    "      if newPrintTask():\n",
    "         task = Task(currentSecond)\n",
    "         printQueue.enqueue(task)\n",
    "\n",
    "      if (not labprinter.busy()) and (not printQueue.isEmpty()):\n",
    "        nexttask = printQueue.dequeue()\n",
    "        waitingtimes.append( nexttask.waitTime(currentSecond))\n",
    "        labprinter.startNext(nexttask)\n",
    "\n",
    "      labprinter.tick()\n",
    "\n",
    "    averageWait=sum(waitingtimes)/len(waitingtimes)\n",
    "    print(\"Average Wait %6.2f secs %3d tasks remaining.\"%(averageWait,printQueue.size()))\n",
    "\n",
    "def newPrintTask():\n",
    "    num = random.randrange(1,181)\n",
    "    if num == 180:\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "for i in range(10):\n",
    "    simulation(3600,5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Deque Abstract Data Type"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<table border=\"0\" class=\"table\" id=\"tbl-dequeoperations\">\n",
    "<caption><strong>Table 1: Examples of Deque Operations</strong></caption>\n",
    "<colgroup>\n",
    "<col width=\"38%\">\n",
    "<col width=\"38%\">\n",
    "<col width=\"24%\">\n",
    "</colgroup>\n",
    "<thead valign=\"bottom\">\n",
    "<tr class=\"row-odd\"><th class=\"head\"><strong>Deque Operation</strong></th>\n",
    "<th class=\"head\"><strong>Deque Contents</strong></th>\n",
    "<th class=\"head\"><strong>Return Value</strong></th>\n",
    "</tr>\n",
    "</thead>\n",
    "<tbody valign=\"top\">\n",
    "<tr class=\"row-even\"><td><code>d.isEmpty()</code></td>\n",
    "<td><code>[]</code></td>\n",
    "<td><code>True</code></td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td><code>d.addRear(4)</code></td>\n",
    "<td><code>[4]</code></td>\n",
    "<td>&nbsp;</td>\n",
    "</tr>\n",
    "<tr class=\"row-even\"><td><code>d.addRear('dog')</code></td>\n",
    "<td><code>['dog',4,]</code></td>\n",
    "<td>&nbsp;</td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td><code>d.addFront('cat')</code></td>\n",
    "<td><code>['dog',4,'cat']</code></td>\n",
    "<td>&nbsp;</td>\n",
    "</tr>\n",
    "<tr class=\"row-even\"><td><code>d.addFront(True)</code></td>\n",
    "<td><code>['dog',4,'cat',True]</code></td>\n",
    "<td>&nbsp;</td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td><code>d.size()</code></td>\n",
    "<td><code>['dog',4,'cat',True]</code></td>\n",
    "<td><code>4</code></td>\n",
    "</tr>\n",
    "<tr class=\"row-even\"><td><code>d.isEmpty()</code></td>\n",
    "<td><code>['dog',4,'cat',True]</code></td>\n",
    "<td><code>False</code></td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td><code>d.addRear(8.4)</code></td>\n",
    "<td><code>[8.4,'dog',4,'cat',True]</code></td>\n",
    "<td>&nbsp;</td>\n",
    "</tr>\n",
    "<tr class=\"row-even\"><td><code>d.removeRear()</code></td>\n",
    "<td><code>['dog',4,'cat',True]</code></td>\n",
    "<td><code>8.4</code></td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td><code>d.removeFront()</code></td>\n",
    "<td><code>['dog',4,'cat']</code></td>\n",
    "<td><code>True</code></td>\n",
    "</tr>\n",
    "</tbody>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementing a Deque in Python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Deque:\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "\n",
    "    def isEmpty(self):\n",
    "        return self.items == []\n",
    "\n",
    "    def addFront(self, item):\n",
    "        self.items.append(item)\n",
    "\n",
    "    def addRear(self, item):\n",
    "        self.items.insert(0,item)\n",
    "\n",
    "    def removeFront(self):\n",
    "        return self.items.pop()\n",
    "\n",
    "    def removeRear(self):\n",
    "        return self.items.pop(0)\n",
    "\n",
    "    def size(self):\n",
    "        return len(self.items)\n",
    "    \n",
    "    def show(self):\n",
    "        return map(lambda x: self.dequeue(), range(self.size()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "4\n",
      "False\n",
      "8.4\n"
     ]
    }
   ],
   "source": [
    "d=Deque()\n",
    "print(d.isEmpty())\n",
    "d.addRear(4)\n",
    "d.addRear('dog')\n",
    "d.addFront('cat')\n",
    "d.addFront(True)\n",
    "print(d.size())\n",
    "print(d.isEmpty())\n",
    "d.addRear(8.4)\n",
    "print(d.removeRear())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Palindrome-Checker(回文检查)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "def palchecker(aString):\n",
    "    chardeque = Deque()\n",
    "\n",
    "    for ch in aString:\n",
    "        chardeque.addRear(ch)\n",
    "\n",
    "    stillEqual = True\n",
    "\n",
    "    while chardeque.size() > 1 and stillEqual:\n",
    "        first = chardeque.removeFront()\n",
    "        last = chardeque.removeRear()\n",
    "        if first != last:\n",
    "            stillEqual = False\n",
    "\n",
    "    return stillEqual\n",
    "\n",
    "print(palchecker(\"lsdkjfskf\"))\n",
    "print(palchecker(\"radar\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Unordered List Abstract Data Type"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- List() creates a new list that is empty. It needs no parameters and returns an empty list.\n",
    "- add(item) adds a new item to the list. It needs the item and returns nothing. Assume the item is not already in the list.\n",
    "- remove(item) removes the item from the list. It needs the item and modifies the list. Assume the item is present in the list.\n",
    "- search(item) searches for the item in the list. It needs the item and returns a boolean value.\n",
    "- isEmpty() tests to see whether the list is empty. It needs no parameters and returns a boolean value.\n",
    "- size() returns the number of items in the list. It needs no parameters and returns an integer.\n",
    "- append(item) adds a new item to the end of the list making it the last item in the collection. It needs the item and returns nothing. Assume the item is not already in the list.\n",
    "- index(item) returns the position of item in the list. It needs the item and returns the index. Assume the item is in the list.\n",
    "- insert(pos,item) adds a new item to the list at position pos. It needs the item and returns nothing. Assume the item is not already in the list and there are enough existing items to have position pos.\n",
    "- pop() removes and returns the last item in the list. It needs nothing and returns an item. Assume the list has at least one item.\n",
    "- pop(pos) removes and returns the item at position pos. It needs the position and returns the item. Assume the item is in the list."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementing an Unordered List: Linked Lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Node:\n",
    "    \"\"\"\n",
    "    The basic building block for the linked list implementation\n",
    "    is the node. Each node object must hold at least two pieces\n",
    "    of information. First, the node must contain the list item \n",
    "    itself. We will call this the data field of the node. \n",
    "    \"\"\"\n",
    "    def __init__(self,initdata):\n",
    "        self.data = initdata\n",
    "        self.next = None\n",
    "\n",
    "    def getData(self):\n",
    "        return self.data\n",
    "\n",
    "    def getNext(self):\n",
    "        return self.next\n",
    "\n",
    "    def setData(self,newdata):\n",
    "        self.data = newdata\n",
    "\n",
    "    def setNext(self,newnext):\n",
    "        self.next = newnext\n",
    "\n",
    "\n",
    "class UnorderedList:\n",
    "    \"\"\"\n",
    "    The unordered list will be built from a collection of nodes, \n",
    "    each linked to the next by explicit references. As long as we \n",
    "    know where to find the first node (containing the first item), \n",
    "    each item after that can be found by successively following \n",
    "    the next links. \n",
    "    \"\"\"\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "\n",
    "    def isEmpty(self):\n",
    "        return self.head == None\n",
    "\n",
    "    def add(self,item):\n",
    "        temp = Node(item)\n",
    "        temp.setNext(self.head)\n",
    "        self.head = temp\n",
    "\n",
    "    def size(self):\n",
    "        current = self.head\n",
    "        count = 0\n",
    "        while current != None:\n",
    "            count = count + 1\n",
    "            current = current.getNext()\n",
    "\n",
    "        return count\n",
    "\n",
    "    def search(self,item):\n",
    "        current = self.head\n",
    "        found = False\n",
    "        while current != None and not found:\n",
    "            if current.getData() == item:\n",
    "                found = True\n",
    "            else:\n",
    "                current = current.getNext()\n",
    "\n",
    "        return found\n",
    "\n",
    "    def remove(self,item):\n",
    "        current = self.head\n",
    "        previous = None\n",
    "        found = False\n",
    "        while not found:\n",
    "            if current.getData() == item:\n",
    "                found = True\n",
    "            else:\n",
    "                previous = current\n",
    "                current = current.getNext()\n",
    "\n",
    "        if previous == None:\n",
    "            self.head = current.getNext()\n",
    "        else:\n",
    "            previous.setNext(current.getNext())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n",
      "True\n",
      "False\n",
      "True\n",
      "7\n",
      "6\n",
      "5\n",
      "4\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "mylist = UnorderedList()\n",
    "\n",
    "mylist.add(31)\n",
    "mylist.add(77)\n",
    "mylist.add(17)\n",
    "mylist.add(93)\n",
    "mylist.add(26)\n",
    "mylist.add(54)\n",
    "\n",
    "print(mylist.size())\n",
    "print(mylist.search(93))\n",
    "print(mylist.search(100))\n",
    "\n",
    "mylist.add(100)\n",
    "print(mylist.search(100))\n",
    "print(mylist.size())\n",
    "\n",
    "mylist.remove(54)\n",
    "print(mylist.size())\n",
    "mylist.remove(93)\n",
    "print(mylist.size())\n",
    "mylist.remove(31)\n",
    "print(mylist.size())\n",
    "print(mylist.search(93))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Ordered List Abstract Data Type"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The structure of an ordered list is a collection of items where each item holds a relative position that is based upon some underlying characteristic of the item. The ordering is typically either ascending or descending and we assume that list items have a meaningful comparison operation that is already defined. Many of the ordered list operations are the same as those of the unordered list.\n",
    "\n",
    "- OrderedList() creates a new ordered list that is empty. It needs no parameters and returns an empty list.\n",
    "- add(item) adds a new item to the list making sure that the order is preserved. It needs the item and returns nothing. Assume the item is not already in the list.\n",
    "- remove(item) removes the item from the list. It needs the item and modifies the list. Assume the item is present in the list.\n",
    "- search(item) searches for the item in the list. It needs the item and returns a boolean value.\n",
    "- isEmpty() tests to see whether the list is empty. It needs no parameters and returns a boolean value.\n",
    "- size() returns the number of items in the list. It needs no parameters and returns an integer.\n",
    "- index(item) returns the position of item in the list. It needs the item and returns the index. Assume the item is in the list.\n",
    "- pop() removes and returns the last item in the list. It needs nothing and returns an item. Assume the list has at least one item.\n",
    "- pop(pos) removes and returns the item at position pos. It needs the position and returns the item. Assume the item is in the list."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementing an Ordered List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class OrderedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "\n",
    "    def search(self,item):\n",
    "        current = self.head\n",
    "        found = False\n",
    "        stop = False\n",
    "        while current != None and not found and not stop:\n",
    "            if current.getData() == item:\n",
    "                found = True\n",
    "            else:\n",
    "                if current.getData() > item:\n",
    "                    stop = True\n",
    "                else:\n",
    "                    current = current.getNext()\n",
    "\n",
    "        return found\n",
    "\n",
    "    def add(self,item):\n",
    "        current = self.head\n",
    "        previous = None\n",
    "        stop = False\n",
    "        while current != None and not stop:\n",
    "            if current.getData() > item:\n",
    "                stop = True\n",
    "            else:\n",
    "                previous = current\n",
    "                current = current.getNext()\n",
    "\n",
    "        temp = Node(item)\n",
    "        if previous == None:\n",
    "            temp.setNext(self.head)\n",
    "            self.head = temp\n",
    "        else:\n",
    "            temp.setNext(current)\n",
    "            previous.setNext(temp)\n",
    "\n",
    "    def isEmpty(self):\n",
    "        return self.head == None\n",
    "\n",
    "    def size(self):\n",
    "        current = self.head\n",
    "        count = 0\n",
    "        while current != None:\n",
    "            count = count + 1\n",
    "            current = current.getNext()\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n",
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "mylist = OrderedList()\n",
    "mylist.add(31)\n",
    "mylist.add(77)\n",
    "mylist.add(17)\n",
    "mylist.add(93)\n",
    "mylist.add(26)\n",
    "mylist.add(54)\n",
    "\n",
    "print(mylist.size())\n",
    "print(mylist.search(93))\n",
    "print(mylist.search(100))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Three Laws of Recursion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. A recursive algorithm must have a base case.\n",
    "2. A recursive algorithm must change its state and move toward the base case.\n",
    "3. A recursive algorithm must call itself, recursively."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "25\n"
     ]
    }
   ],
   "source": [
    "def listsum(numList):\n",
    "    theSum = 0\n",
    "    for i in numList:\n",
    "        theSum = theSum + i\n",
    "    return theSum\n",
    "\n",
    "print(listsum([1,3,5,7,9]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "25\n"
     ]
    }
   ],
   "source": [
    "def listsum(numList):\n",
    "   if len(numList) == 1:\n",
    "        return numList[0]\n",
    "   else:\n",
    "        return numList[0] + listsum(numList[1:])\n",
    "\n",
    "print(listsum([1,3,5,7,9]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Converting an Integer to a String in Any Base"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5AD\n"
     ]
    }
   ],
   "source": [
    "def toStr(n,base):\n",
    "   convertString = \"0123456789ABCDEF\"\n",
    "   if n < base:\n",
    "      return convertString[n]\n",
    "   else:\n",
    "      return toStr(n//base,base) + convertString[n%base]\n",
    "\n",
    "print(toStr(1453,16))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def reverse(s):\n",
    "    \"\"\"\n",
    "    a function that takes a string as a parameter and returns\n",
    "    a new string that is the reverse of the old string.\n",
    "    \"\"\"\n",
    "    if s == '': return s\n",
    "    else: return reverse(s[1:]) + s[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "wollof\n",
      "+ a\n"
     ]
    }
   ],
   "source": [
    "print(reverse(\"follow\"))\n",
    "print(reverse(\"a +\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import string\n",
    "\n",
    "def removeWhite(s):\n",
    "    exclude = set(string.punctuation+' ')\n",
    "    s = ''.join(ch for ch in s if ch not in exclude)\n",
    "    return s\n",
    "\n",
    "def isPal(s):\n",
    "    \"\"\"\n",
    "    Write a function that takes a string as a parameter and\n",
    "    returns True if the string is a palindrome, False otherwise. \n",
    "    \"\"\"\n",
    "    s = removeWhite(s)\n",
    "    return len(s) < 2 or s[0] == s[-1] and isPal(s[1:-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "True\n",
      "False\n",
      "True\n",
      "True\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "print(isPal(removeWhite(\"x\")))\n",
    "print(isPal(removeWhite(\"radar\")))\n",
    "print(isPal(removeWhite(\"hello\")))\n",
    "print(isPal(removeWhite(\"\")))\n",
    "print(isPal(removeWhite(\"hannah\")))\n",
    "print(isPal(removeWhite(\"madam i'm adam\")))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Stack Frames: Implementing Recursion"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5AD\n"
     ]
    }
   ],
   "source": [
    "rStack = Stack()\n",
    "\n",
    "def toStr(n,base):\n",
    "    convertString = \"0123456789ABCDEF\"\n",
    "    while n > 0:\n",
    "        if n < base:\n",
    "            rStack.push(convertString[n])\n",
    "        else:\n",
    "            rStack.push(convertString[n % base])\n",
    "        n = n // base\n",
    "    res = \"\"\n",
    "    while not rStack.isEmpty():\n",
    "        res = res + str(rStack.pop())\n",
    "    return res\n",
    "\n",
    "print(toStr(1453,16))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<iframe width=\"1000\" height=\"500\" frameborder=\"0\" src=\"http://pythontutor.com/iframe-embed.html#code=class+Stack%3A%0A++++def+__init__(self)%3A%0A++++++++self.items+%3D+%5B%5D%0A%0A++++def+isEmpty(self)%3A%0A++++++++return+self.items+%3D%3D+%5B%5D%0A%0A++++def+push(self,+item)%3A%0A++++++++self.items.append(item)%0A%0A++++def+pop(self)%3A%0A++++++++return+self.items.pop()%0A%0A++++def+peek(self)%3A%0A++++++++return+self.items%5Blen(self.items)-1%5D%0A%0A++++def+size(self)%3A%0A++++++++return+len(self.items)%0A++++%0ArStack+%3D+Stack()%0A%0Adef+toStr(n,base)%3A%0A++++convertString+%3D+%220123456789ABCDEF%22%0A++++while+n+%3E+0%3A%0A++++++++if+n+%3C+base%3A%0A++++++++++++rStack.push(convertString%5Bn%5D)%0A++++++++else%3A%0A++++++++++++rStack.push(convertString%5Bn+%25+base%5D)%0A++++++++n+%3D+n+//+base%0A++++res+%3D+%22%22%0A++++while+not+rStack.isEmpty()%3A%0A++++++++res+%3D+res+%2B+str(rStack.pop())%0A++++return+res%0A%0Aprint(toStr(1453,16))&origin=opt-frontend.js&cumulative=false&heapPrimitives=false&drawParentPointers=false&textReferences=false&showOnlyOutputs=false&py=2&rawInputLstJSON=%5B%5D&curInstr=29&codeDivWidth=350&codeDivHeight=400\"> </iframe>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML at 0x7f83a45bba20>"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "HTML('<iframe width=\"1000\" height=\"500\" frameborder=\"0\" src=\"http://pythontutor.com/iframe-embed.html#code=class+Stack%3A%0A++++def+__init__(self)%3A%0A++++++++self.items+%3D+%5B%5D%0A%0A++++def+isEmpty(self)%3A%0A++++++++return+self.items+%3D%3D+%5B%5D%0A%0A++++def+push(self,+item)%3A%0A++++++++self.items.append(item)%0A%0A++++def+pop(self)%3A%0A++++++++return+self.items.pop()%0A%0A++++def+peek(self)%3A%0A++++++++return+self.items%5Blen(self.items)-1%5D%0A%0A++++def+size(self)%3A%0A++++++++return+len(self.items)%0A++++%0ArStack+%3D+Stack()%0A%0Adef+toStr(n,base)%3A%0A++++convertString+%3D+%220123456789ABCDEF%22%0A++++while+n+%3E+0%3A%0A++++++++if+n+%3C+base%3A%0A++++++++++++rStack.push(convertString%5Bn%5D)%0A++++++++else%3A%0A++++++++++++rStack.push(convertString%5Bn+%25+base%5D)%0A++++++++n+%3D+n+//+base%0A++++res+%3D+%22%22%0A++++while+not+rStack.isEmpty()%3A%0A++++++++res+%3D+res+%2B+str(rStack.pop())%0A++++return+res%0A%0Aprint(toStr(1453,16))&origin=opt-frontend.js&cumulative=false&heapPrimitives=false&drawParentPointers=false&textReferences=false&showOnlyOutputs=false&py=2&rawInputLstJSON=%5B%5D&curInstr=29&codeDivWidth=350&codeDivHeight=400\"> </iframe>')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tower of Hanoi"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The number of moves required to correctly move a tower of $n$ disks is $2^n-1$.Here is a high-level outline of how to move a tower from the starting pole, to the goal pole, using an intermediate pole:\n",
    "\n",
    "1. Move a tower of height-1 to an intermediate pole, using the final pole. 用C把高度height-1的塔从A移动到B\n",
    "2. Move the remaining disk to the final pole. 把A剩下的碟子移动到C\n",
    "3. Move the tower of height-1 from the intermediate pole to the final pole using the original pole. 用A把高度height-1的塔从B移动到C\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "moving disk from A to B\n",
      "moving disk from A to C\n",
      "moving disk from B to C\n",
      "moving disk from A to B\n",
      "moving disk from C to A\n",
      "moving disk from C to B\n",
      "moving disk from A to B\n"
     ]
    }
   ],
   "source": [
    "def moveTower(height,fromPole, toPole, withPole):\n",
    "    if height >= 1:\n",
    "        moveTower(height-1,fromPole,withPole,toPole)\n",
    "        moveDisk(fromPole,toPole)\n",
    "        moveTower(height-1,withPole,toPole,fromPole)\n",
    "\n",
    "def moveDisk(fp,tp):\n",
    "    print(\"moving disk from\",fp,\"to\",tp)\n",
    "\n",
    "moveTower(3,\"A\",\"B\",\"C\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<iframe width=\"1000\" height=\"500\" frameborder=\"0\" src=\"http://pythontutor.com/iframe-embed.html#code=def+moveTower(height,fromPole,+toPole,+withPole)%3A%0A++++if+height+%3E%3D+1%3A%0A++++++++moveTower(height-1,fromPole,withPole,toPole)%0A++++++++moveDisk(fromPole,toPole)%0A++++++++moveTower(height-1,withPole,toPole,fromPole)%0A%0Adef+moveDisk(fp,tp)%3A%0A++++print+%22moving+disk+from%22,fp,%22to%22,tp%0A%0AmoveTower(3,%22A%22,%22B%22,%22C%22)&origin=opt-frontend.js&cumulative=false&heapPrimitives=false&drawParentPointers=false&textReferences=false&showOnlyOutputs=false&py=2&rawInputLstJSON=%5B%5D&curInstr=80&codeDivWidth=350&codeDivHeight=400\"> </iframe>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML at 0x7f83a45bbda0>"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "HTML('<iframe width=\"1000\" height=\"500\" frameborder=\"0\" src=\"http://pythontutor.com/iframe-embed.html#code=def+moveTower(height,fromPole,+toPole,+withPole)%3A%0A++++if+height+%3E%3D+1%3A%0A++++++++moveTower(height-1,fromPole,withPole,toPole)%0A++++++++moveDisk(fromPole,toPole)%0A++++++++moveTower(height-1,withPole,toPole,fromPole)%0A%0Adef+moveDisk(fp,tp)%3A%0A++++print+%22moving+disk+from%22,fp,%22to%22,tp%0A%0AmoveTower(3,%22A%22,%22B%22,%22C%22)&origin=opt-frontend.js&cumulative=false&heapPrimitives=false&drawParentPointers=false&textReferences=false&showOnlyOutputs=false&py=2&rawInputLstJSON=%5B%5D&curInstr=80&codeDivWidth=350&codeDivHeight=400\"> </iframe>')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "moveTower: 3 ('A', [3, 2, 1]) ('C', []) ('B', [])\n",
      "moveTower: 2 ('A', [3, 2, 1]) ('B', []) ('C', [])\n",
      "moveTower: 1 ('A', [3, 2, 1]) ('C', []) ('B', [])\n",
      "moveTower: 0 ('A', [3, 2, 1]) ('B', []) ('C', [])\n",
      "moving 1 from A to C\n",
      "moveTower: 0 ('B', []) ('C', [1]) ('A', [3, 2])\n",
      "moving 2 from A to C\n",
      "moveTower: 1 ('C', [1, 2]) ('B', []) ('A', [3])\n",
      "moveTower: 0 ('C', [1, 2]) ('A', [3]) ('B', [])\n",
      "moving 3 from A to C\n",
      "moveTower: 0 ('A', []) ('B', []) ('C', [1, 2, 3])\n",
      "moveTower: 2 ('B', []) ('C', [1, 2, 3]) ('A', [])\n",
      "moveTower: 1 ('B', []) ('A', []) ('C', [1, 2, 3])\n",
      "moveTower: 0 ('B', []) ('C', [1, 2, 3]) ('A', [])\n",
      "moveTower: 0 ('C', [1, 2, 3]) ('A', []) ('B', [])\n",
      "moveTower: 1 ('A', []) ('C', [1, 2, 3]) ('B', [])\n",
      "moveTower: 0 ('A', []) ('B', []) ('C', [1, 2, 3])\n",
      "moveTower: 0 ('B', []) ('C', [1, 2, 3]) ('A', [])\n",
      "('A', []) ('B', []) ('C', [1, 2, 3])\n"
     ]
    }
   ],
   "source": [
    "def moveTower(height,fromPole, toPole, withPole):\n",
    "    print(\"moveTower:\", height,fromPole, toPole, withPole)\n",
    "    if height >= 1:\n",
    "        moveTower(height-1,fromPole,withPole,toPole)\n",
    "        moveDisk(fromPole,toPole)\n",
    "        moveTower(height-1,withPole,toPole,fromPole)\n",
    "\n",
    "def moveDisk(fp,tp):\n",
    "    if fromPole[1]:\n",
    "        disk = fromPole[1].pop()\n",
    "        print(\"moving \" + str(disk) + \" from \" + fromPole[0] + \" to \" + toPole[0])\n",
    "        toPole[1].append(disk)\n",
    "    \n",
    "fromPole = (\"A\", [3,2,1])\n",
    "toPole = (\"C\", [])\n",
    "withPole = (\"B\", [])\n",
    "\n",
    "moveTower(len(fromPole[1]), fromPole, toPole, withPole)\n",
    "print(fromPole, withPole, toPole)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exploring a Maze"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import turtle\n",
    "from __future__ import division\n",
    "\n",
    "PART_OF_PATH = 'O'\n",
    "TRIED = '.'\n",
    "OBSTACLE = '+'\n",
    "DEAD_END = '-'\n",
    "\n",
    "class Maze:\n",
    "    def __init__(self,mazeFileName):\n",
    "        rowsInMaze = 0\n",
    "        columnsInMaze = 0\n",
    "        self.mazelist = []\n",
    "        mazeFile = open(mazeFileName,'r')\n",
    "        rowsInMaze = 0\n",
    "        for line in mazeFile:\n",
    "            rowList = []\n",
    "            col = 0\n",
    "            for ch in line[:-1]:\n",
    "                rowList.append(ch)\n",
    "                if ch == 'S':\n",
    "                    self.startRow = rowsInMaze\n",
    "                    self.startCol = col\n",
    "                col = col + 1\n",
    "            rowsInMaze = rowsInMaze + 1\n",
    "            self.mazelist.append(rowList)\n",
    "            columnsInMaze = len(rowList)\n",
    "\n",
    "        self.rowsInMaze = rowsInMaze\n",
    "        self.columnsInMaze = columnsInMaze\n",
    "        self.xTranslate = -columnsInMaze/2\n",
    "        self.yTranslate = rowsInMaze/2\n",
    "        self.t = turtle.Turtle()\n",
    "        self.t.shape('turtle')\n",
    "        self.wn = turtle.Screen()\n",
    "        self.wn.setworldcoordinates(-(columnsInMaze-1)/2-.5,-(rowsInMaze-1)/2-.5,(columnsInMaze-1)/2+.5,(rowsInMaze-1)/2+.5)\n",
    "\n",
    "    def drawMaze(self):\n",
    "        self.t.speed(10)\n",
    "        for y in range(self.rowsInMaze):\n",
    "            for x in range(self.columnsInMaze):\n",
    "                if self.mazelist[y][x] == OBSTACLE:\n",
    "                    self.drawCenteredBox(x+self.xTranslate,-y+self.yTranslate,'orange')\n",
    "        self.t.color('black')\n",
    "        self.t.fillcolor('blue')\n",
    "\n",
    "    def drawCenteredBox(self,x,y,color):\n",
    "        self.t.up()\n",
    "        self.t.goto(x-.5,y-.5)\n",
    "        self.t.color(color)\n",
    "        self.t.fillcolor(color)\n",
    "        self.t.setheading(90)\n",
    "        self.t.down()\n",
    "        self.t.begin_fill()\n",
    "        for i in range(4):\n",
    "            self.t.forward(1)\n",
    "            self.t.right(90)\n",
    "        self.t.end_fill()\n",
    "\n",
    "    def moveTurtle(self,x,y):\n",
    "        self.t.up()\n",
    "        self.t.setheading(self.t.towards(x+self.xTranslate,-y+self.yTranslate))\n",
    "        self.t.goto(x+self.xTranslate,-y+self.yTranslate)\n",
    "\n",
    "    def dropBreadcrumb(self,color):\n",
    "        self.t.dot(10,color)\n",
    "\n",
    "    def updatePosition(self,row,col,val=None):\n",
    "        if val:\n",
    "            self.mazelist[row][col] = val\n",
    "        self.moveTurtle(col,row)\n",
    "\n",
    "        if val == PART_OF_PATH:\n",
    "            color = 'green'\n",
    "        elif val == OBSTACLE:\n",
    "            color = 'red'\n",
    "        elif val == TRIED:\n",
    "            color = 'black'\n",
    "        elif val == DEAD_END:\n",
    "            color = 'red'\n",
    "        else:\n",
    "            color = None\n",
    "\n",
    "        if color:\n",
    "            self.dropBreadcrumb(color)\n",
    "\n",
    "    def isExit(self,row,col):\n",
    "        return (row == 0 or\n",
    "                row == self.rowsInMaze-1 or\n",
    "                col == 0 or\n",
    "                col == self.columnsInMaze-1 )\n",
    "\n",
    "    def __getitem__(self,idx):\n",
    "        return self.mazelist[idx]\n",
    "\n",
    "\n",
    "def searchFrom(maze, startRow, startColumn):\n",
    "    # try each of four directions from this point until we find a way out.\n",
    "    # base Case return values:\n",
    "    #  1. We have run into an obstacle, return false\n",
    "    maze.updatePosition(startRow, startColumn)\n",
    "    if maze[startRow][startColumn] == OBSTACLE :\n",
    "        return False\n",
    "    #  2. We have found a square that has already been explored\n",
    "    if maze[startRow][startColumn] == TRIED or maze[startRow][startColumn] == DEAD_END:\n",
    "        return False\n",
    "    # 3. We have found an outside edge not occupied by an obstacle\n",
    "    if maze.isExit(startRow,startColumn):\n",
    "        maze.updatePosition(startRow, startColumn, PART_OF_PATH)\n",
    "        return True\n",
    "    maze.updatePosition(startRow, startColumn, TRIED)\n",
    "    # Otherwise, use logical short circuiting to try each direction\n",
    "    # in turn (if needed)\n",
    "    found = searchFrom(maze, startRow-1, startColumn) or \\\n",
    "            searchFrom(maze, startRow+1, startColumn) or \\\n",
    "            searchFrom(maze, startRow, startColumn-1) or \\\n",
    "            searchFrom(maze, startRow, startColumn+1)\n",
    "    if found:\n",
    "        maze.updatePosition(startRow, startColumn, PART_OF_PATH)\n",
    "    else:\n",
    "        maze.updatePosition(startRow, startColumn, DEAD_END)\n",
    "    return found\n",
    "\n",
    "\n",
    "# myMaze = Maze('maze2.txt')\n",
    "# myMaze.drawMaze()\n",
    "# myMaze.updatePosition(myMaze.startRow,myMaze.startCol)\n",
    "\n",
    "# searchFrom(myMaze, myMaze.startRow, myMaze.startCol)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Dynamic Programming"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n"
     ]
    }
   ],
   "source": [
    "def recDC(coinValueList,change,knownResults):\n",
    "   minCoins = change\n",
    "   if change in coinValueList:\n",
    "      knownResults[change] = 1\n",
    "      return 1\n",
    "   elif knownResults[change] > 0:\n",
    "      return knownResults[change]\n",
    "   else:\n",
    "       for i in [c for c in coinValueList if c <= change]:\n",
    "         numCoins = 1 + recDC(coinValueList, change-i,\n",
    "                              knownResults)\n",
    "         if numCoins < minCoins:\n",
    "            minCoins = numCoins\n",
    "            knownResults[change] = minCoins\n",
    "   return minCoins\n",
    "\n",
    "print(recDC([1,5,10,25],63,[0]*64))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Making change for 63 requires\n",
      "3 coins\n",
      "They are:\n",
      "21\n",
      "21\n",
      "21\n",
      "The used list is as follows:\n",
      "[1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 10, 1, 1, 1, 1, 5, 1, 1, 1, 1, 10, 21, 1, 1, 1, 25, 1, 1, 1, 1, 5, 10, 1, 1, 1, 10, 1, 1, 1, 1, 5, 10, 21, 1, 1, 10, 21, 1, 1, 1, 25, 1, 10, 1, 1, 5, 10, 1, 1, 1, 10, 1, 10, 21]\n"
     ]
    }
   ],
   "source": [
    "def dpMakeChange(coinValueList,change,minCoins,coinsUsed):\n",
    "   for cents in range(change+1):\n",
    "      coinCount = cents\n",
    "      newCoin = 1\n",
    "      for j in [c for c in coinValueList if c <= cents]:\n",
    "            if minCoins[cents-j] + 1 < coinCount:\n",
    "               coinCount = minCoins[cents-j]+1\n",
    "               newCoin = j\n",
    "      minCoins[cents] = coinCount\n",
    "      coinsUsed[cents] = newCoin\n",
    "   return minCoins[change]\n",
    "\n",
    "def printCoins(coinsUsed,change):\n",
    "   coin = change\n",
    "   while coin > 0:\n",
    "      thisCoin = coinsUsed[coin]\n",
    "      print(thisCoin)\n",
    "      coin = coin - thisCoin\n",
    "\n",
    "def main():\n",
    "    amnt = 63\n",
    "    clist = [1,5,10,21,25]\n",
    "    coinsUsed = [0]*(amnt+1)\n",
    "    coinCount = [0]*(amnt+1)\n",
    "\n",
    "    print(\"Making change for\",amnt,\"requires\")\n",
    "    print(dpMakeChange(clist,amnt,coinCount,coinsUsed),\"coins\")\n",
    "    print(\"They are:\")\n",
    "    printCoins(coinsUsed,amnt)\n",
    "    print(\"The used list is as follows:\")\n",
    "    print(coinsUsed)\n",
    "\n",
    "main()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. All recursive algorithms must have a base case.\n",
    "2. A recursive algorithm must change its state and make progress toward the base case.\n",
    "3. A recursive algorithm must call itself (recursively).\n",
    "4. Recursion can take the place of iteration in some cases.\n",
    "5. Recursive algorithms often map very naturally to a formal expression of the problem you are trying to solve.\n",
    "6. Recursion is not always the answer. Sometimes a recursive solution may be more computationally expensive than an alternative algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Sequential Search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<table border=\"0\" class=\"table\" id=\"tbl-seqsearchtable\">\n",
    "<caption><strong>Table 1: Comparisons Used in a Sequential Search of an Unordered List</strong></caption>\n",
    "<colgroup>\n",
    "<col width=\"21%\">\n",
    "<col width=\"27%\">\n",
    "<col width=\"27%\">\n",
    "<col width=\"25%\">\n",
    "</colgroup>\n",
    "<thead valign=\"bottom\">\n",
    "<tr class=\"row-odd\"><th class=\"head\"><strong>Case</strong></th>\n",
    "<th class=\"head\"><strong>Best Case</strong></th>\n",
    "<th class=\"head\"><strong>Worst Case</strong></th>\n",
    "<th class=\"head\"><strong>Average Case</strong></th>\n",
    "</tr>\n",
    "</thead>\n",
    "<tbody valign=\"top\">\n",
    "<tr class=\"row-even\"><td>item is present</td>\n",
    "<td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-5-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-18\" style=\"width: 0.647em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 0.53em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.876em 1000.003em 2.872em -0.465em); top: -2.69em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-19\"><span class=\"mn\" id=\"MathJax-Span-20\" style=\"font-family: MathJax_Main;\">1</span></span><span style=\"display: inline-block; width: 0px; height: 2.696em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.932em; vertical-align: -0.068em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-5\">1</script></span></td>\n",
    "<td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-6-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-21\" style=\"width: 0.823em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 0.647em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.818em 1000.003em 2.638em -0.524em); top: -2.456em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-22\"><span class=\"mi\" id=\"MathJax-Span-23\" style=\"font-family: MathJax_Math; font-style: italic;\">n</span></span><span style=\"display: inline-block; width: 0px; height: 2.462em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.718em; vertical-align: -0.068em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-6\">n</script></span></td>\n",
    "<td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-7-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-24\" style=\"width: 0.94em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 0.764em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.174em 1000.003em 2.696em -0.524em); top: -2.105em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-25\"><span class=\"mfrac\" id=\"MathJax-Span-26\"><span style=\"display: inline-block; position: relative; width: 0.53em; height: 0px; margin-right: 0.12em; margin-left: 0.12em;\"><span style=\"position: absolute; clip: rect(1.759em 1000.003em 2.403em -0.524em); top: -2.632em; left: 50%; margin-left: -0.173em;\"><span class=\"mi\" id=\"MathJax-Span-27\" style=\"font-size: 70.7%; font-family: MathJax_Math; font-style: italic;\">n</span><span style=\"display: inline-block; width: 0px; height: 2.228em;\"></span></span><span style=\"position: absolute; clip: rect(1.642em 1000.003em 2.462em -0.465em); top: -1.871em; left: 50%; margin-left: -0.173em;\"><span class=\"mn\" id=\"MathJax-Span-28\" style=\"font-size: 70.7%; font-family: MathJax_Main;\">2</span><span style=\"display: inline-block; width: 0px; height: 2.286em;\"></span></span><span style=\"position: absolute; clip: rect(0.823em 1000.003em 1.232em -0.524em); top: -1.285em; left: 0.003em;\"><span style=\"border-left-width: 0.53em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.25px; vertical-align: 0.003em;\"></span><span style=\"display: inline-block; width: 0px; height: 1.057em;\"></span></span></span></span></span><span style=\"display: inline-block; width: 0px; height: 2.111em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.504em; vertical-align: -0.568em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-7\">\\frac{n}{2}</script></span></td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td>item is not present</td>\n",
    "<td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-8-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-29\" style=\"width: 0.823em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 0.647em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.818em 1000.003em 2.638em -0.524em); top: -2.456em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-30\"><span class=\"mi\" id=\"MathJax-Span-31\" style=\"font-family: MathJax_Math; font-style: italic;\">n</span></span><span style=\"display: inline-block; width: 0px; height: 2.462em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.718em; vertical-align: -0.068em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-8\">n</script></span></td>\n",
    "<td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-9-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-32\" style=\"width: 0.823em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 0.647em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.818em 1000.003em 2.638em -0.524em); top: -2.456em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-33\"><span class=\"mi\" id=\"MathJax-Span-34\" style=\"font-family: MathJax_Math; font-style: italic;\">n</span></span><span style=\"display: inline-block; width: 0px; height: 2.462em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.718em; vertical-align: -0.068em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-9\">n</script></span></td>\n",
    "<td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-10-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-35\" style=\"width: 0.823em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 0.647em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.818em 1000.003em 2.638em -0.524em); top: -2.456em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-36\"><span class=\"mi\" id=\"MathJax-Span-37\" style=\"font-family: MathJax_Math; font-style: italic;\">n</span></span><span style=\"display: inline-block; width: 0px; height: 2.462em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.718em; vertical-align: -0.068em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-10\">n</script></span></td>\n",
    "</tr>\n",
    "</tbody>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "def sequentialSearch(alist, item):\n",
    "    pos = 0\n",
    "    found = False\n",
    "\n",
    "    while pos < len(alist) and not found:\n",
    "        if alist[pos] == item:\n",
    "            found = True\n",
    "        else:\n",
    "            pos = pos + 1\n",
    "\n",
    "    return found\n",
    "\n",
    "testlist = [1, 2, 32, 8, 17, 19, 42, 13, 0]\n",
    "print(sequentialSearch(testlist, 3))\n",
    "print(sequentialSearch(testlist, 13))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<table border=\"0\" class=\"table\" id=\"tbl-seqsearchtable2\">\n",
    "<caption><strong>Table 2: Comparisons Used in Sequential Search of an Ordered List</strong></caption>\n",
    "<colgroup>\n",
    "<col width=\"25%\">\n",
    "<col width=\"22%\">\n",
    "<col width=\"22%\">\n",
    "<col width=\"30%\">\n",
    "</colgroup>\n",
    "<thead valign=\"bottom\">\n",
    "<tr class=\"row-odd\"><th class=\"head\">&nbsp;</th>\n",
    "<th class=\"head\"><strong>Best Case</strong></th>\n",
    "<th class=\"head\"><strong>Worst Case</strong></th>\n",
    "<th class=\"head\"><strong>Average Case</strong></th>\n",
    "</tr>\n",
    "</thead>\n",
    "<tbody valign=\"top\">\n",
    "<tr class=\"row-even\"><td>item is present</td>\n",
    "<td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-13-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-49\" style=\"width: 0.647em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 0.53em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.876em 1000.003em 2.872em -0.465em); top: -2.69em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-50\"><span class=\"mn\" id=\"MathJax-Span-51\" style=\"font-family: MathJax_Main;\">1</span></span><span style=\"display: inline-block; width: 0px; height: 2.696em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.932em; vertical-align: -0.068em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-13\">1</script></span></td>\n",
    "<td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-14-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-52\" style=\"width: 0.823em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 0.647em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.818em 1000.003em 2.638em -0.524em); top: -2.456em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-53\"><span class=\"mi\" id=\"MathJax-Span-54\" style=\"font-family: MathJax_Math; font-style: italic;\">n</span></span><span style=\"display: inline-block; width: 0px; height: 2.462em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.718em; vertical-align: -0.068em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-14\">n</script></span></td>\n",
    "<td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-15-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-55\" style=\"width: 0.94em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 0.764em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.174em 1000.003em 2.696em -0.524em); top: -2.105em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-56\"><span class=\"mfrac\" id=\"MathJax-Span-57\"><span style=\"display: inline-block; position: relative; width: 0.53em; height: 0px; margin-right: 0.12em; margin-left: 0.12em;\"><span style=\"position: absolute; clip: rect(1.759em 1000.003em 2.403em -0.524em); top: -2.632em; left: 50%; margin-left: -0.173em;\"><span class=\"mi\" id=\"MathJax-Span-58\" style=\"font-size: 70.7%; font-family: MathJax_Math; font-style: italic;\">n</span><span style=\"display: inline-block; width: 0px; height: 2.228em;\"></span></span><span style=\"position: absolute; clip: rect(1.642em 1000.003em 2.462em -0.465em); top: -1.871em; left: 50%; margin-left: -0.173em;\"><span class=\"mn\" id=\"MathJax-Span-59\" style=\"font-size: 70.7%; font-family: MathJax_Main;\">2</span><span style=\"display: inline-block; width: 0px; height: 2.286em;\"></span></span><span style=\"position: absolute; clip: rect(0.823em 1000.003em 1.232em -0.524em); top: -1.285em; left: 0.003em;\"><span style=\"border-left-width: 0.53em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.25px; vertical-align: 0.003em;\"></span><span style=\"display: inline-block; width: 0px; height: 1.057em;\"></span></span></span></span></span><span style=\"display: inline-block; width: 0px; height: 2.111em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.504em; vertical-align: -0.568em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-15\">\\frac{n}{2}</script></span></td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td>item not present</td>\n",
    "<td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-16-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-60\" style=\"width: 0.647em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 0.53em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.876em 1000.003em 2.872em -0.465em); top: -2.69em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-61\"><span class=\"mn\" id=\"MathJax-Span-62\" style=\"font-family: MathJax_Main;\">1</span></span><span style=\"display: inline-block; width: 0px; height: 2.696em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.932em; vertical-align: -0.068em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-16\">1</script></span></td>\n",
    "<td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-17-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-63\" style=\"width: 0.823em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 0.647em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.818em 1000.003em 2.638em -0.524em); top: -2.456em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-64\"><span class=\"mi\" id=\"MathJax-Span-65\" style=\"font-family: MathJax_Math; font-style: italic;\">n</span></span><span style=\"display: inline-block; width: 0px; height: 2.462em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.718em; vertical-align: -0.068em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-17\">n</script></span></td>\n",
    "<td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-18-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-66\" style=\"width: 0.94em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 0.764em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.174em 1000.003em 2.696em -0.524em); top: -2.105em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-67\"><span class=\"mfrac\" id=\"MathJax-Span-68\"><span style=\"display: inline-block; position: relative; width: 0.53em; height: 0px; margin-right: 0.12em; margin-left: 0.12em;\"><span style=\"position: absolute; clip: rect(1.759em 1000.003em 2.403em -0.524em); top: -2.632em; left: 50%; margin-left: -0.173em;\"><span class=\"mi\" id=\"MathJax-Span-69\" style=\"font-size: 70.7%; font-family: MathJax_Math; font-style: italic;\">n</span><span style=\"display: inline-block; width: 0px; height: 2.228em;\"></span></span><span style=\"position: absolute; clip: rect(1.642em 1000.003em 2.462em -0.465em); top: -1.871em; left: 50%; margin-left: -0.173em;\"><span class=\"mn\" id=\"MathJax-Span-70\" style=\"font-size: 70.7%; font-family: MathJax_Main;\">2</span><span style=\"display: inline-block; width: 0px; height: 2.286em;\"></span></span><span style=\"position: absolute; clip: rect(0.823em 1000.003em 1.232em -0.524em); top: -1.285em; left: 0.003em;\"><span style=\"border-left-width: 0.53em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.25px; vertical-align: 0.003em;\"></span><span style=\"display: inline-block; width: 0px; height: 1.057em;\"></span></span></span></span></span><span style=\"display: inline-block; width: 0px; height: 2.111em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.504em; vertical-align: -0.568em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-18\">\\frac{n}{2}</script></span></td>\n",
    "</tr>\n",
    "</tbody>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "def orderedSequentialSearch(alist, item):\n",
    "    pos = 0\n",
    "    found = False\n",
    "    stop = False\n",
    "    while pos < len(alist) and not found and not stop:\n",
    "        if alist[pos] == item:\n",
    "            found = True\n",
    "        else:\n",
    "            if alist[pos] > item:\n",
    "                stop = True\n",
    "            else:\n",
    "                pos = pos+1\n",
    "\n",
    "    return found\n",
    "\n",
    "testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]\n",
    "print(orderedSequentialSearch(testlist, 3))\n",
    "print(orderedSequentialSearch(testlist, 13))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Binary Search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<table border=\"0\" class=\"table\" id=\"tbl-binaryanalysis\">\n",
    "<caption><strong>Table 3: Tabular Analysis for a Binary Search</strong></caption>\n",
    "<colgroup>\n",
    "<col width=\"39%\">\n",
    "<col width=\"61%\">\n",
    "</colgroup>\n",
    "<thead valign=\"bottom\">\n",
    "<tr class=\"row-odd\"><th class=\"head\"><strong>Comparisons</strong></th>\n",
    "<th class=\"head\"><strong>Approximate Number of Items Left</strong></th>\n",
    "</tr>\n",
    "</thead>\n",
    "<tbody valign=\"top\">\n",
    "<tr class=\"row-even\"><td>1</td>\n",
    "<td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-6-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-26\" style=\"width: 0.94em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 0.764em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.174em 1000.003em 2.696em -0.524em); top: -2.105em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-27\"><span class=\"mfrac\" id=\"MathJax-Span-28\"><span style=\"display: inline-block; position: relative; width: 0.53em; height: 0px; margin-right: 0.12em; margin-left: 0.12em;\"><span style=\"position: absolute; clip: rect(1.759em 1000.003em 2.403em -0.524em); top: -2.632em; left: 50%; margin-left: -0.173em;\"><span class=\"mi\" id=\"MathJax-Span-29\" style=\"font-size: 70.7%; font-family: MathJax_Math; font-style: italic;\">n</span><span style=\"display: inline-block; width: 0px; height: 2.228em;\"></span></span><span style=\"position: absolute; clip: rect(1.642em 1000.003em 2.462em -0.465em); top: -1.871em; left: 50%; margin-left: -0.173em;\"><span class=\"mn\" id=\"MathJax-Span-30\" style=\"font-size: 70.7%; font-family: MathJax_Main;\">2</span><span style=\"display: inline-block; width: 0px; height: 2.286em;\"></span></span><span style=\"position: absolute; clip: rect(0.823em 1000.003em 1.232em -0.524em); top: -1.285em; left: 0.003em;\"><span style=\"border-left-width: 0.53em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.25px; vertical-align: 0.003em;\"></span><span style=\"display: inline-block; width: 0px; height: 1.057em;\"></span></span></span></span></span><span style=\"display: inline-block; width: 0px; height: 2.111em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.504em; vertical-align: -0.568em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-6\">\\frac {n}{2}</script></span></td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td>2</td>\n",
    "<td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-7-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-31\" style=\"width: 0.94em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 0.764em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.174em 1000.003em 2.696em -0.524em); top: -2.105em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-32\"><span class=\"mfrac\" id=\"MathJax-Span-33\"><span style=\"display: inline-block; position: relative; width: 0.53em; height: 0px; margin-right: 0.12em; margin-left: 0.12em;\"><span style=\"position: absolute; clip: rect(1.759em 1000.003em 2.403em -0.524em); top: -2.632em; left: 50%; margin-left: -0.173em;\"><span class=\"mi\" id=\"MathJax-Span-34\" style=\"font-size: 70.7%; font-family: MathJax_Math; font-style: italic;\">n</span><span style=\"display: inline-block; width: 0px; height: 2.228em;\"></span></span><span style=\"position: absolute; clip: rect(1.642em 1000.003em 2.462em -0.524em); top: -1.871em; left: 50%; margin-left: -0.173em;\"><span class=\"mn\" id=\"MathJax-Span-35\" style=\"font-size: 70.7%; font-family: MathJax_Main;\">4</span><span style=\"display: inline-block; width: 0px; height: 2.286em;\"></span></span><span style=\"position: absolute; clip: rect(0.823em 1000.003em 1.232em -0.524em); top: -1.285em; left: 0.003em;\"><span style=\"border-left-width: 0.53em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.25px; vertical-align: 0.003em;\"></span><span style=\"display: inline-block; width: 0px; height: 1.057em;\"></span></span></span></span></span><span style=\"display: inline-block; width: 0px; height: 2.111em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.504em; vertical-align: -0.568em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-7\">\\frac {n}{4}</script></span></td>\n",
    "</tr>\n",
    "<tr class=\"row-even\"><td>3</td>\n",
    "<td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-8-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-36\" style=\"width: 0.94em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 0.764em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.174em 1000.003em 2.696em -0.524em); top: -2.105em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-37\"><span class=\"mfrac\" id=\"MathJax-Span-38\"><span style=\"display: inline-block; position: relative; width: 0.53em; height: 0px; margin-right: 0.12em; margin-left: 0.12em;\"><span style=\"position: absolute; clip: rect(1.759em 1000.003em 2.403em -0.524em); top: -2.632em; left: 50%; margin-left: -0.173em;\"><span class=\"mi\" id=\"MathJax-Span-39\" style=\"font-size: 70.7%; font-family: MathJax_Math; font-style: italic;\">n</span><span style=\"display: inline-block; width: 0px; height: 2.228em;\"></span></span><span style=\"position: absolute; clip: rect(1.642em 1000.003em 2.462em -0.465em); top: -1.871em; left: 50%; margin-left: -0.173em;\"><span class=\"mn\" id=\"MathJax-Span-40\" style=\"font-size: 70.7%; font-family: MathJax_Main;\">8</span><span style=\"display: inline-block; width: 0px; height: 2.286em;\"></span></span><span style=\"position: absolute; clip: rect(0.823em 1000.003em 1.232em -0.524em); top: -1.285em; left: 0.003em;\"><span style=\"border-left-width: 0.53em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.25px; vertical-align: 0.003em;\"></span><span style=\"display: inline-block; width: 0px; height: 1.057em;\"></span></span></span></span></span><span style=\"display: inline-block; width: 0px; height: 2.111em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.575em; vertical-align: -0.568em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-8\">\\frac {n}{8}</script></span></td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td>...</td>\n",
    "<td>&nbsp;</td>\n",
    "</tr>\n",
    "<tr class=\"row-even\"><td>i</td>\n",
    "<td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-9-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-41\" style=\"width: 1.232em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 0.998em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.174em 1000.003em 2.813em -0.524em); top: -2.105em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-42\"><span class=\"mfrac\" id=\"MathJax-Span-43\"><span style=\"display: inline-block; position: relative; width: 0.764em; height: 0px; margin-right: 0.12em; margin-left: 0.12em;\"><span style=\"position: absolute; clip: rect(1.759em 1000.003em 2.403em -0.524em); top: -2.632em; left: 50%; margin-left: -0.173em;\"><span class=\"mi\" id=\"MathJax-Span-44\" style=\"font-size: 70.7%; font-family: MathJax_Math; font-style: italic;\">n</span><span style=\"display: inline-block; width: 0px; height: 2.228em;\"></span></span><span style=\"position: absolute; clip: rect(3.223em 1000.003em 4.16em -0.465em); top: -3.451em; left: 50%; margin-left: -0.29em;\"><span class=\"msubsup\" id=\"MathJax-Span-45\"><span style=\"display: inline-block; position: relative; width: 0.647em; height: 0px;\"><span style=\"position: absolute; clip: rect(1.642em 1000.003em 2.462em -0.465em); top: -2.28em; left: 0.003em;\"><span class=\"mn\" id=\"MathJax-Span-46\" style=\"font-size: 70.7%; font-family: MathJax_Main;\">2</span><span style=\"display: inline-block; width: 0px; height: 2.286em;\"></span></span><span style=\"position: absolute; top: -2.398em; left: 0.413em;\"><span class=\"mi\" id=\"MathJax-Span-47\" style=\"font-size: 50%; font-family: MathJax_Math; font-style: italic;\">i</span><span style=\"display: inline-block; width: 0px; height: 2.111em;\"></span></span></span></span><span style=\"display: inline-block; width: 0px; height: 3.984em;\"></span></span><span style=\"position: absolute; clip: rect(0.823em 1000.003em 1.232em -0.524em); top: -1.285em; left: 0.003em;\"><span style=\"border-left-width: 0.764em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.25px; vertical-align: 0.003em;\"></span><span style=\"display: inline-block; width: 0px; height: 1.057em;\"></span></span></span></span></span><span style=\"display: inline-block; width: 0px; height: 2.111em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.718em; vertical-align: -0.711em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-9\">\\frac {n}{2^i}</script></span></td>\n",
    "</tr>\n",
    "</tbody>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Binary Search of an Ordered List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "def binarySearch(alist, item):\n",
    "    first = 0\n",
    "    last = len(alist) - 1\n",
    "    found = False\n",
    "\n",
    "    while first <= last and not found:\n",
    "        midpoint = (first + last) // 2\n",
    "        if alist[midpoint] == item:\n",
    "            found = True\n",
    "        else:\n",
    "            if item < alist[midpoint]:\n",
    "                last = midpoint-1\n",
    "            else:\n",
    "                first = midpoint+1\n",
    "\n",
    "    return found\n",
    "\n",
    "testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]\n",
    "print(binarySearch(testlist, 3))\n",
    "print(binarySearch(testlist, 13))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### A Binary Search--Recursive Version"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "def binarySearch(alist, item):\n",
    "    if len(alist) == 0:\n",
    "        return False\n",
    "    else:\n",
    "        midpoint = len(alist) // 2\n",
    "        if alist[midpoint] == item:\n",
    "            return True\n",
    "        else:\n",
    "            if item < alist[midpoint]:\n",
    "                return binarySearch(alist[:midpoint], item)\n",
    "            else:\n",
    "                return binarySearch(alist[midpoint + 1:], item)\n",
    "\n",
    "testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42, ]\n",
    "print(binarySearch(testlist, 3))\n",
    "print(binarySearch(testlist, 13))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Hashing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Map() Create a new, empty map. It returns an empty map collection.\n",
    "- put(key,val) Add a new key-value pair to the map. If the key is already in the map then replace the old value with the new value.\n",
    "- get(key) Given a key, return the value stored in the map or None otherwise.\n",
    "- del Delete the key-value pair from the map using a statement of the form del map[key].\n",
    "- len() Return the number of key-value pairs stored in the map.\n",
    "- in Return True for a statement of the form key in map, if the given key is in the map, False otherwise."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class HashTable:\n",
    "    def __init__(self):\n",
    "        self.size = 11\n",
    "        self.slots = [None] * self.size\n",
    "        self.data = [None] * self.size\n",
    "        \n",
    "    def put(self,key,data):\n",
    "      hashvalue = self.hashfunction(key,len(self.slots))\n",
    "\n",
    "      if self.slots[hashvalue] == None:\n",
    "        self.slots[hashvalue] = key\n",
    "        self.data[hashvalue] = data\n",
    "      else:\n",
    "        if self.slots[hashvalue] == key:\n",
    "          self.data[hashvalue] = data  #replace\n",
    "        else:\n",
    "          nextslot = self.rehash(hashvalue,len(self.slots))\n",
    "          while self.slots[nextslot] != None and \\\n",
    "                          self.slots[nextslot] != key:\n",
    "            nextslot = self.rehash(nextslot,len(self.slots))\n",
    "\n",
    "          if self.slots[nextslot] == None:\n",
    "            self.slots[nextslot]=key\n",
    "            self.data[nextslot]=data\n",
    "          else:\n",
    "            self.data[nextslot] = data #replace\n",
    "\n",
    "    def hashfunction(self,key,size):\n",
    "         return key%size\n",
    "\n",
    "    def rehash(self,oldhash,size):\n",
    "        return (oldhash+1)%size\n",
    "\n",
    "    def get(self,key):\n",
    "      startslot = self.hashfunction(key,len(self.slots))\n",
    "\n",
    "      data = None\n",
    "      stop = False\n",
    "      found = False\n",
    "      position = startslot\n",
    "      while self.slots[position] != None and  \\\n",
    "                           not found and not stop:\n",
    "         if self.slots[position] == key:\n",
    "           found = True\n",
    "           data = self.data[position]\n",
    "         else:\n",
    "           position=self.rehash(position,len(self.slots))\n",
    "           if position == startslot:\n",
    "               stop = True\n",
    "      return data\n",
    "\n",
    "    def __getitem__(self,key):\n",
    "        return self.get(key)\n",
    "\n",
    "    def __setitem__(self,key,data):\n",
    "        self.put(key,data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[77, 44, 55, 20, 26, 93, 17, None, None, 31, 54]\n",
      "['bird', 'goat', 'pig', 'chicken', 'dog', 'lion', 'tiger', None, None, 'cow', 'cat']\n",
      "chicken\n",
      "tiger\n",
      "duck\n",
      "None\n"
     ]
    }
   ],
   "source": [
    "H=HashTable()\n",
    "H[54]=\"cat\"\n",
    "H[26]=\"dog\"\n",
    "H[93]=\"lion\"\n",
    "H[17]=\"tiger\"\n",
    "H[77]=\"bird\"\n",
    "H[31]=\"cow\"\n",
    "H[44]=\"goat\"\n",
    "H[55]=\"pig\"\n",
    "H[20]=\"chicken\"\n",
    "print(H.slots)\n",
    "print(H.data)\n",
    "\n",
    "print(H[20])\n",
    "\n",
    "print(H[17])\n",
    "H[20]='duck'\n",
    "print(H[20])\n",
    "print(H[99])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Bubble Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[17, 20, 26, 31, 44, 54, 55, 77, 93]\n"
     ]
    }
   ],
   "source": [
    "def bubbleSort(alist):\n",
    "    for passnum in range(len(alist)-1,0,-1):\n",
    "        for i in range(passnum):\n",
    "            if alist[i]>alist[i+1]:\n",
    "                temp = alist[i]\n",
    "                alist[i] = alist[i+1]\n",
    "                alist[i+1] = temp\n",
    "\n",
    "alist = [54,26,93,17,77,31,44,55,20]\n",
    "bubbleSort(alist)\n",
    "print(alist)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The Short Bubble Sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A bubble sort can be modified to stop early if it finds that the list has become sorted. This means that for lists that require just a few passes, a bubble sort may have an advantage in that it will recognize the sorted list and stop. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[20, 30, 40, 50, 60, 70, 80, 90, 100, 110]\n"
     ]
    }
   ],
   "source": [
    "def shortBubbleSort(alist):\n",
    "    exchanges = True\n",
    "    passnum = len(alist)-1\n",
    "    while passnum > 0 and exchanges:\n",
    "       exchanges = False\n",
    "       for i in range(passnum):\n",
    "           if alist[i]>alist[i+1]:\n",
    "               exchanges = True\n",
    "               temp = alist[i]\n",
    "               alist[i] = alist[i+1]\n",
    "               alist[i+1] = temp\n",
    "       passnum = passnum-1\n",
    "\n",
    "alist=[20,30,40,90,50,60,70,80,100,110]\n",
    "shortBubbleSort(alist)\n",
    "print(alist)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Selection Sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Selection sort improves upon bubble sort by making fewer swaps"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[17, 20, 26, 31, 44, 54, 55, 77, 93]\n"
     ]
    }
   ],
   "source": [
    "def selectionSort(alist):\n",
    "   for fillslot in range(len(alist)-1,0,-1):\n",
    "       positionOfMax=0\n",
    "       for location in range(1,fillslot+1):\n",
    "           if alist[location]>alist[positionOfMax]:\n",
    "               positionOfMax = location\n",
    "\n",
    "       temp = alist[fillslot]\n",
    "       alist[fillslot] = alist[positionOfMax]\n",
    "       alist[positionOfMax] = temp\n",
    "\n",
    "alist = [54,26,93,17,77,31,44,55,20]\n",
    "selectionSort(alist)\n",
    "print(alist)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Insertion Sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Insertion sort works at the start of the list. Each pass produces a longer sorted list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[17, 20, 26, 31, 44, 54, 55, 77, 93]\n"
     ]
    }
   ],
   "source": [
    "def insertionSort(alist):\n",
    "   for index in range(1,len(alist)):\n",
    "\n",
    "     currentvalue = alist[index]\n",
    "     position = index\n",
    "\n",
    "     while position>0 and alist[position-1]>currentvalue:\n",
    "         alist[position]=alist[position-1]\n",
    "         position = position-1\n",
    "\n",
    "     alist[position]=currentvalue\n",
    "\n",
    "alist = [54,26,93,17,77,31,44,55,20]\n",
    "insertionSort(alist)\n",
    "print(alist)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Shell Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "After increments of size 4 The list is [20, 26, 44, 17, 54, 31, 93, 55, 77]\n",
      "After increments of size 2 The list is [20, 17, 44, 26, 54, 31, 77, 55, 93]\n",
      "After increments of size 1 The list is [17, 20, 26, 31, 44, 54, 55, 77, 93]\n",
      "[17, 20, 26, 31, 44, 54, 55, 77, 93]\n"
     ]
    }
   ],
   "source": [
    "def shellSort(alist):\n",
    "    sublistcount = len(alist) // 2\n",
    "    while sublistcount > 0:\n",
    "\n",
    "      for startposition in range(sublistcount):\n",
    "        gapInsertionSort(alist,startposition,sublistcount)\n",
    "\n",
    "      print(\"After increments of size\",sublistcount, \"The list is\", alist)\n",
    "\n",
    "      sublistcount = sublistcount // 2\n",
    "\n",
    "def gapInsertionSort(alist,start,gap):\n",
    "    for i in range(start+gap,len(alist),gap):\n",
    "\n",
    "        currentvalue = alist[i]\n",
    "        position = i\n",
    "\n",
    "        while position>=gap and alist[position-gap]>currentvalue:\n",
    "            alist[position]=alist[position-gap]\n",
    "            position = position-gap\n",
    "\n",
    "        alist[position]=currentvalue\n",
    "\n",
    "alist = [54,26,93,17,77,31,44,55,20]\n",
    "shellSort(alist)\n",
    "print(alist)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Merge Sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Merge sort will continue to recursively move toward the beginning of the list until it hits a base case."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Splitting  [54, 26, 93, 17, 77, 31, 44, 55, 20]\n",
      "Splitting  [54, 26, 93, 17]\n",
      "Splitting  [54, 26]\n",
      "Splitting  [54]\n",
      "Merging  [54]\n",
      "Splitting  [26]\n",
      "Merging  [26]\n",
      "Merging  [26, 54]\n",
      "Splitting  [93, 17]\n",
      "Splitting  [93]\n",
      "Merging  [93]\n",
      "Splitting  [17]\n",
      "Merging  [17]\n",
      "Merging  [17, 93]\n",
      "Merging  [17, 26, 54, 93]\n",
      "Splitting  [77, 31, 44, 55, 20]\n",
      "Splitting  [77, 31]\n",
      "Splitting  [77]\n",
      "Merging  [77]\n",
      "Splitting  [31]\n",
      "Merging  [31]\n",
      "Merging  [31, 77]\n",
      "Splitting  [44, 55, 20]\n",
      "Splitting  [44]\n",
      "Merging  [44]\n",
      "Splitting  [55, 20]\n",
      "Splitting  [55]\n",
      "Merging  [55]\n",
      "Splitting  [20]\n",
      "Merging  [20]\n",
      "Merging  [20, 55]\n",
      "Merging  [20, 44, 55]\n",
      "Merging  [20, 31, 44, 55, 77]\n",
      "Merging  [17, 20, 26, 31, 44, 54, 55, 77, 93]\n",
      "[17, 20, 26, 31, 44, 54, 55, 77, 93]\n"
     ]
    }
   ],
   "source": [
    "def mergeSort(alist):\n",
    "    print(\"Splitting \",alist)\n",
    "    if len(alist)>1:\n",
    "        mid = len(alist)//2\n",
    "        lefthalf = alist[:mid]\n",
    "        righthalf = alist[mid:]\n",
    "\n",
    "        mergeSort(lefthalf)\n",
    "        mergeSort(righthalf)\n",
    "\n",
    "        i=0\n",
    "        j=0\n",
    "        k=0\n",
    "        while i<len(lefthalf) and j<len(righthalf):\n",
    "            if lefthalf[i]<righthalf[j]:\n",
    "                alist[k]=lefthalf[i]\n",
    "                i=i+1\n",
    "            else:\n",
    "                alist[k]=righthalf[j]\n",
    "                j=j+1\n",
    "            k=k+1\n",
    "\n",
    "        while i<len(lefthalf):\n",
    "            alist[k]=lefthalf[i]\n",
    "            i=i+1\n",
    "            k=k+1\n",
    "\n",
    "        while j<len(righthalf):\n",
    "            alist[k]=righthalf[j]\n",
    "            j=j+1\n",
    "            k=k+1\n",
    "    print(\"Merging \",alist)\n",
    "\n",
    "alist = [54,26,93,17,77,31,44,55,20]\n",
    "mergeSort(alist)\n",
    "print(alist)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Quick Sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To choose the pivot value, we will consider the first, the middle, and the last element in the list. In our example, those are 54, 77, and 20. Now pick the median value, in our case 54, and use it for the pivot value (of course, that was the pivot value we used originally). The idea is that in the case where the the first item in the list does not belong toward the middle of the list, the median of three will choose a better “middle” value. This will be particularly useful when the original list is somewhat sorted to begin with. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[17, 20, 26, 31, 44, 54, 55, 77, 93]\n"
     ]
    }
   ],
   "source": [
    "def quickSort(alist):\n",
    "   quickSortHelper(alist,0,len(alist)-1)\n",
    "\n",
    "def quickSortHelper(alist,first,last):\n",
    "   if first<last:\n",
    "\n",
    "       splitpoint = partition(alist,first,last)\n",
    "\n",
    "       quickSortHelper(alist,first,splitpoint-1)\n",
    "       quickSortHelper(alist,splitpoint+1,last)\n",
    "\n",
    "\n",
    "def partition(alist,first,last):\n",
    "   pivotvalue = alist[first]\n",
    "\n",
    "   leftmark = first+1\n",
    "   rightmark = last\n",
    "\n",
    "   done = False\n",
    "   while not done:\n",
    "\n",
    "       while leftmark <= rightmark and \\\n",
    "               alist[leftmark] <= pivotvalue:\n",
    "           leftmark = leftmark + 1\n",
    "\n",
    "       while alist[rightmark] >= pivotvalue and \\\n",
    "               rightmark >= leftmark:\n",
    "           rightmark = rightmark -1\n",
    "\n",
    "       if rightmark < leftmark:\n",
    "           done = True\n",
    "       else:\n",
    "           temp = alist[leftmark]\n",
    "           alist[leftmark] = alist[rightmark]\n",
    "           alist[rightmark] = temp\n",
    "\n",
    "   temp = alist[first]\n",
    "   alist[first] = alist[rightmark]\n",
    "   alist[rightmark] = temp\n",
    "\n",
    "\n",
    "   return rightmark\n",
    "\n",
    "alist = [54,26,93,17,77,31,44,55,20]\n",
    "quickSort(alist)\n",
    "print(alist)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. A sequential search is $O(n)$ for ordered and unordered lists.\n",
    "2. A binary search of an ordered list is $O(logn)$ in the worst case.\n",
    "3. Hash tables can provide constant time searching.\n",
    "4. A bubble sort, a selection sort, and an insertion sort are $O(n^2)$ algorithms.\n",
    "5. A shell sort improves on the insertion sort by sorting incremental sublists. It falls between $O(n)$ and $O(n^2)$.\n",
    "6. A merge sort is $O(nlogn)$, but requires additional space for the merging process.\n",
    "7. A quick sort is $O(nlogn)$, but may degrade to $O(n^2)$ if the split points are not near the middle of the list. It does not require additional space."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Trees and Tree Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Definition One: A tree consists of a set of nodes and a set of edges that connect pairs of nodes. A tree has the following properties:\n",
    "    - One node of the tree is designated as the root node.\n",
    "    - Every node n, except the root node, is connected by an edge from exactly one other node p, where p is the parent of n.\n",
    "    - A unique path traverses from the root to each node.\n",
    "    - If each node in the tree has a maximum of two children, we say that the tree is a binary tree.\n",
    "2. Definition Two: A tree is either empty or consists of a root and zero or more subtrees, each of which is also a tree. The root of each subtree is connected to the root of the parent tree by an edge. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## List of Lists Representation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['a', ['b', ['d', [], []], ['e', [], []]], ['c', ['f', [], []], []]]\n",
      "left subtree =  ['b', ['d', [], []], ['e', [], []]]\n",
      "root =  a\n",
      "right subtree =  ['c', ['f', [], []], []]\n"
     ]
    }
   ],
   "source": [
    "myTree = ['a', ['b', ['d',[],[]], ['e',[],[]] ], ['c', ['f',[],[]], []] ]\n",
    "print(myTree)\n",
    "print('left subtree = ', myTree[1])\n",
    "print('root = ', myTree[0])\n",
    "print('right subtree = ', myTree[2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### A Python Session to Illustrate Basic Tree Functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5, [4, [], []], []]\n",
      "[3, [9, [4, [], []], []], [7, [], [6, [], []]]]\n",
      "[3, [9, [11, [4, [], []], []], []], [7, [], [6, [], []]]]\n",
      "[6, [], []]\n"
     ]
    }
   ],
   "source": [
    "def BinaryTree(r):\n",
    "    return [r, [], []]\n",
    "\n",
    "def insertLeft(root,newBranch):\n",
    "    t = root.pop(1)\n",
    "    if len(t) > 1:\n",
    "        root.insert(1,[newBranch,t,[]])\n",
    "    else:\n",
    "        root.insert(1,[newBranch, [], []])\n",
    "    return root\n",
    "\n",
    "def insertRight(root,newBranch):\n",
    "    t = root.pop(2)\n",
    "    if len(t) > 1:\n",
    "        root.insert(2,[newBranch,[],t])\n",
    "    else:\n",
    "        root.insert(2,[newBranch,[],[]])\n",
    "    return root\n",
    "\n",
    "def getRootVal(root):\n",
    "    return root[0]\n",
    "\n",
    "def setRootVal(root,newVal):\n",
    "    root[0] = newVal\n",
    "\n",
    "def getLeftChild(root):\n",
    "    return root[1]\n",
    "\n",
    "def getRightChild(root):\n",
    "    return root[2]\n",
    "\n",
    "r = BinaryTree(3)\n",
    "insertLeft(r,4)\n",
    "insertLeft(r,5)\n",
    "insertRight(r,6)\n",
    "insertRight(r,7)\n",
    "l = getLeftChild(r)\n",
    "print(l)\n",
    "\n",
    "setRootVal(l,9)\n",
    "print(r)\n",
    "insertLeft(l,11)\n",
    "print(r)\n",
    "print(getRightChild(getRightChild(r)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['a', ['b', [], []], ['c', [], ['d', ['e', [], []], []]]]\n"
     ]
    }
   ],
   "source": [
    "x = BinaryTree('a')\n",
    "insertLeft(x,'b')\n",
    "insertRight(x,'c')\n",
    "insertRight(getRightChild(x),'d')\n",
    "insertLeft(getRightChild(getRightChild(x)),'e')\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Nodes and References"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class BinaryTree:\n",
    "    def __init__(self,rootObj):\n",
    "        self.key = rootObj\n",
    "        self.leftChild = None\n",
    "        self.rightChild = None\n",
    "\n",
    "    def insertLeft(self,newNode):\n",
    "        if self.leftChild == None:\n",
    "            self.leftChild = BinaryTree(newNode)\n",
    "        else:\n",
    "            t = BinaryTree(newNode)\n",
    "            t.leftChild = self.leftChild\n",
    "            self.leftChild = t\n",
    "\n",
    "    def insertRight(self,newNode):\n",
    "        if self.rightChild == None:\n",
    "            self.rightChild = BinaryTree(newNode)\n",
    "        else:\n",
    "            t = BinaryTree(newNode)\n",
    "            t.rightChild = self.rightChild\n",
    "            self.rightChild = t\n",
    "\n",
    "\n",
    "    def getRightChild(self):\n",
    "        return self.rightChild\n",
    "\n",
    "    def getLeftChild(self):\n",
    "        return self.leftChild\n",
    "\n",
    "    def setRootVal(self,obj):\n",
    "        self.key = obj\n",
    "\n",
    "    def getRootVal(self):\n",
    "        return self.key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a\n",
      "None\n",
      "<__main__.BinaryTree object at 0x7f83a44e9c88>\n",
      "b\n",
      "<__main__.BinaryTree object at 0x7f83a44e5898>\n",
      "c\n",
      "hello\n"
     ]
    }
   ],
   "source": [
    "r = BinaryTree('a')\n",
    "print(r.getRootVal())\n",
    "print(r.getLeftChild())\n",
    "r.insertLeft('b')\n",
    "print(r.getLeftChild())\n",
    "print(r.getLeftChild().getRootVal())\n",
    "r.insertRight('c')\n",
    "print(r.getRightChild())\n",
    "print(r.getRightChild().getRootVal())\n",
    "r.getRightChild().setRootVal('hello')\n",
    "print(r.getRightChild().getRootVal())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Parse Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. If the current token is a `'('`, add a new node as the left child of the current node, and descend to the left child.\n",
    "2. If the current token is in the list `['+','-','/','*']`, set the root value of the current node to the operator represented by the current token. Add a new node as the right child of the current node and descend to the right child.\n",
    "3. If the current token is a number, set the root value of the current node to the number and return to the parent.\n",
    "4. If the current token is a `')'`, go to the parent of the current node."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "7\n",
      "9\n",
      "(((4)+(5))*(7))\n",
      "63\n",
      "2\n",
      "10\n",
      "5\n",
      "+\n",
      "3\n",
      "*\n"
     ]
    }
   ],
   "source": [
    "from pythonds.basic.stack import Stack\n",
    "from pythonds.trees.binaryTree import BinaryTree\n",
    "def buildParseTree(fpexp):\n",
    "    fplist = fpexp.split()\n",
    "    pStack = Stack()\n",
    "    eTree = BinaryTree('')\n",
    "    pStack.push(eTree)\n",
    "    currentTree = eTree\n",
    "    for i in fplist:\n",
    "        if i == '(':\n",
    "            currentTree.insertLeft('')\n",
    "            pStack.push(currentTree)\n",
    "            currentTree = currentTree.getLeftChild()\n",
    "        elif i not in ['+', '-', '*', '/', ')']:\n",
    "            currentTree.setRootVal(int(i))\n",
    "            parent = pStack.pop()\n",
    "            currentTree = parent\n",
    "        elif i in ['+', '-', '*', '/']:\n",
    "            currentTree.setRootVal(i)\n",
    "            currentTree.insertRight('')\n",
    "            pStack.push(currentTree)\n",
    "            currentTree = currentTree.getRightChild()\n",
    "        elif i == ')':\n",
    "            currentTree = pStack.pop()\n",
    "        else:\n",
    "            raise ValueError\n",
    "    return eTree\n",
    "pt = buildParseTree(\"( ( 10 + 5 ) * 3 )\")\n",
    "pt.postorder()  #defined and explained in the next section"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "45"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import operator\n",
    "def evaluate(parseTree):\n",
    "    opers = {'+':operator.add, '-':operator.sub, '*':operator.mul, '/':operator.truediv}\n",
    "\n",
    "    leftC = parseTree.getLeftChild()\n",
    "    rightC = parseTree.getRightChild()\n",
    "\n",
    "    if leftC and rightC:\n",
    "        fn = opers[parseTree.getRootVal()]\n",
    "        return fn(evaluate(leftC),evaluate(rightC))\n",
    "    else:\n",
    "        return parseTree.getRootVal()\n",
    "\n",
    "evaluate(pt)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tree Traversals"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. **preorder**. In a preorder traversal, we visit the root node first, then recursively do a preorder traversal of the left subtree, followed by a recursive preorder traversal of the right subtree.\n",
    "2. **inorder**. In an inorder traversal, we recursively do an inorder traversal on the left subtree, visit the root node, and finally do a recursive inorder traversal of the right subtree.\n",
    "3. **postorder**. In a postorder traversal, we recursively do a postorder traversal of the left subtree and the right subtree followed by a visit to the root node."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "*\n",
      "+\n",
      "10\n",
      "5\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "def preorder(tree):\n",
    "    if tree:\n",
    "        print(tree.getRootVal())\n",
    "        preorder(tree.getLeftChild())\n",
    "        preorder(tree.getRightChild())\n",
    "\n",
    "preorder(pt)        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def preorder(self):\n",
    "    print(self.key)\n",
    "    if self.leftChild:\n",
    "        self.left.preorder()\n",
    "    if self.rightChild:\n",
    "        self.right.preorder()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n",
      "5\n",
      "+\n",
      "3\n",
      "*\n"
     ]
    }
   ],
   "source": [
    "def postorder(tree):\n",
    "    if tree != None:\n",
    "        postorder(tree.getLeftChild())\n",
    "        postorder(tree.getRightChild())\n",
    "        print(tree.getRootVal())\n",
    "\n",
    "postorder(pt)        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "45"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def postordereval(tree):\n",
    "    opers = {'+':operator.add, '-':operator.sub, '*':operator.mul, '/':operator.truediv}\n",
    "    res1 = None\n",
    "    res2 = None\n",
    "    if tree:\n",
    "        res1 = postordereval(tree.getLeftChild())\n",
    "        res2 = postordereval(tree.getRightChild())\n",
    "        if res1 and res2:\n",
    "            return opers[tree.getRootVal()](res1,res2)\n",
    "        else:\n",
    "            return tree.getRootVal()\n",
    "        \n",
    "postordereval(pt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n",
      "+\n",
      "5\n",
      "*\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "def inorder(tree):\n",
    "  if tree != None:\n",
    "      inorder(tree.getLeftChild())\n",
    "      print(tree.getRootVal())\n",
    "      inorder(tree.getRightChild())\n",
    "\n",
    "inorder(pt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'(((10)+(5))*(3))'"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def printexp(tree):\n",
    "  sVal = \"\"\n",
    "  if tree:\n",
    "      sVal = '(' + printexp(tree.getLeftChild())\n",
    "      sVal = sVal + str(tree.getRootVal())\n",
    "      sVal = sVal + printexp(tree.getRightChild())+')'\n",
    "  return sVal\n",
    "\n",
    "printexp(pt)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Priority Queues with Binary Heaps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A **priority queue** acts like a queue in that you dequeue an item by removing it from the front. However, in a priority queue the logical order of items inside a queue is determined by their priority. The highest priority items are at the front of the queue and the lowest priority items are at the back. Thus when you enqueue an item on a priority queue, the new item may move all the way to the front. \n",
    "\n",
    "The classic way to implement a priority queue is using a data structure called a **binary heap**. A binary heap will allow us both enqueue and dequeue items in $O(logn)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary Heap Operations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- BinaryHeap() creates a new, empty, binary heap.\n",
    "- insert(k) adds a new item to the heap.\n",
    "- findMin() returns the item with the minimum key value, leaving item in the heap.\n",
    "- delMin() returns the item with the minimum key value, removing the item from the heap.\n",
    "- isEmpty() returns true if the heap is empty, false otherwise.\n",
    "- size() returns the number of items in the heap.\n",
    "- buildHeap(list) builds a new heap from a list of keys."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "5\n",
      "7\n",
      "11\n"
     ]
    }
   ],
   "source": [
    "from pythonds.trees.binheap import BinHeap\n",
    "\n",
    "bh = BinHeap()\n",
    "bh.insert(5)\n",
    "bh.insert(7)\n",
    "bh.insert(3)\n",
    "bh.insert(11)\n",
    "\n",
    "print(bh.delMin())\n",
    "print(bh.delMin())\n",
    "print(bh.delMin())\n",
    "print(bh.delMin())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary Heap Implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "3\n",
      "5\n",
      "6\n",
      "9\n"
     ]
    }
   ],
   "source": [
    "class BinHeap:\n",
    "    def __init__(self):\n",
    "        self.heapList = [0]\n",
    "        self.currentSize = 0\n",
    "\n",
    "\n",
    "    def percUp(self,i):\n",
    "        while i // 2 > 0:\n",
    "          if self.heapList[i] < self.heapList[i // 2]:\n",
    "             tmp = self.heapList[i // 2]\n",
    "             self.heapList[i // 2] = self.heapList[i]\n",
    "             self.heapList[i] = tmp\n",
    "          i = i // 2\n",
    "\n",
    "    def insert(self,k):\n",
    "      self.heapList.append(k)\n",
    "      self.currentSize = self.currentSize + 1\n",
    "      self.percUp(self.currentSize)\n",
    "\n",
    "    def percDown(self,i):\n",
    "      while (i * 2) <= self.currentSize:\n",
    "          mc = self.minChild(i)\n",
    "          if self.heapList[i] > self.heapList[mc]:\n",
    "              tmp = self.heapList[i]\n",
    "              self.heapList[i] = self.heapList[mc]\n",
    "              self.heapList[mc] = tmp\n",
    "          i = mc\n",
    "\n",
    "    def minChild(self,i):\n",
    "      if i * 2 + 1 > self.currentSize:\n",
    "          return i * 2\n",
    "      else:\n",
    "          if self.heapList[i*2] < self.heapList[i*2+1]:\n",
    "              return i * 2\n",
    "          else:\n",
    "              return i * 2 + 1\n",
    "\n",
    "    def delMin(self):\n",
    "      retval = self.heapList[1]\n",
    "      self.heapList[1] = self.heapList[self.currentSize]\n",
    "      self.currentSize = self.currentSize - 1\n",
    "      self.heapList.pop()\n",
    "      self.percDown(1)\n",
    "      return retval\n",
    "\n",
    "    def buildHeap(self,alist):\n",
    "      i = len(alist) // 2\n",
    "      self.currentSize = len(alist)\n",
    "      self.heapList = [0] + alist[:]\n",
    "      while (i > 0):\n",
    "          self.percDown(i)\n",
    "          i = i - 1\n",
    "\n",
    "bh = BinHeap()\n",
    "bh.buildHeap([9,5,6,2,3])\n",
    "\n",
    "print(bh.delMin())\n",
    "print(bh.delMin())\n",
    "print(bh.delMin())\n",
    "print(bh.delMin())\n",
    "print(bh.delMin())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary Search Tree Operations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Map() Create a new, empty map.\n",
    "- put(key,val) Add a new key-value pair to the map. If the key is already in the map then replace the old value with the new value.\n",
    "- get(key) Given a key, return the value stored in the map or None otherwise.\n",
    "- del Delete the key-value pair from the map using a statement of the form del map[key].\n",
    "- len() Return the number of key-value pairs stored in the map.\n",
    "- in Return True for a statement of the form key in map, if the given key is in the map."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "yellow\n",
      "at\n"
     ]
    }
   ],
   "source": [
    "class TreeNode:\n",
    "    def __init__(self,key,val,left=None,right=None,parent=None):\n",
    "        self.key = key\n",
    "        self.payload = val\n",
    "        self.leftChild = left\n",
    "        self.rightChild = right\n",
    "        self.parent = parent\n",
    "\n",
    "    def hasLeftChild(self):\n",
    "        return self.leftChild\n",
    "\n",
    "    def hasRightChild(self):\n",
    "        return self.rightChild\n",
    "\n",
    "    def isLeftChild(self):\n",
    "        return self.parent and self.parent.leftChild == self\n",
    "\n",
    "    def isRightChild(self):\n",
    "        return self.parent and self.parent.rightChild == self\n",
    "\n",
    "    def isRoot(self):\n",
    "        return not self.parent\n",
    "\n",
    "    def isLeaf(self):\n",
    "        return not (self.rightChild or self.leftChild)\n",
    "\n",
    "    def hasAnyChildren(self):\n",
    "        return self.rightChild or self.leftChild\n",
    "\n",
    "    def hasBothChildren(self):\n",
    "        return self.rightChild and self.leftChild\n",
    "\n",
    "    def replaceNodeData(self,key,value,lc,rc):\n",
    "        self.key = key\n",
    "        self.payload = value\n",
    "        self.leftChild = lc\n",
    "        self.rightChild = rc\n",
    "        if self.hasLeftChild():\n",
    "            self.leftChild.parent = self\n",
    "        if self.hasRightChild():\n",
    "            self.rightChild.parent = self\n",
    "\n",
    "\n",
    "class BinarySearchTree:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.root = None\n",
    "        self.size = 0\n",
    "\n",
    "    def length(self):\n",
    "        return self.size\n",
    "\n",
    "    def __len__(self):\n",
    "        return self.size\n",
    "\n",
    "    def put(self,key,val):\n",
    "        if self.root:\n",
    "            self._put(key,val,self.root)\n",
    "        else:\n",
    "            self.root = TreeNode(key,val)\n",
    "        self.size = self.size + 1\n",
    "\n",
    "    def _put(self,key,val,currentNode):\n",
    "        if key < currentNode.key:\n",
    "            if currentNode.hasLeftChild():\n",
    "                   self._put(key,val,currentNode.leftChild)\n",
    "            else:\n",
    "                   currentNode.leftChild = TreeNode(key,val,parent=currentNode)\n",
    "        else:\n",
    "            if currentNode.hasRightChild():\n",
    "                   self._put(key,val,currentNode.rightChild)\n",
    "            else:\n",
    "                   currentNode.rightChild = TreeNode(key,val,parent=currentNode)\n",
    "\n",
    "    def __setitem__(self,k,v):\n",
    "       self.put(k,v)\n",
    "\n",
    "    def get(self,key):\n",
    "       if self.root:\n",
    "           res = self._get(key,self.root)\n",
    "           if res:\n",
    "                  return res.payload\n",
    "           else:\n",
    "                  return None\n",
    "       else:\n",
    "           return None\n",
    "\n",
    "    def _get(self,key,currentNode):\n",
    "       if not currentNode:\n",
    "           return None\n",
    "       elif currentNode.key == key:\n",
    "           return currentNode\n",
    "       elif key < currentNode.key:\n",
    "           return self._get(key,currentNode.leftChild)\n",
    "       else:\n",
    "           return self._get(key,currentNode.rightChild)\n",
    "\n",
    "    def __getitem__(self,key):\n",
    "       return self.get(key)\n",
    "\n",
    "    def __contains__(self,key):\n",
    "       if self._get(key,self.root):\n",
    "           return True\n",
    "       else:\n",
    "           return False\n",
    "\n",
    "    def delete(self,key):\n",
    "      if self.size > 1:\n",
    "         nodeToRemove = self._get(key,self.root)\n",
    "         if nodeToRemove:\n",
    "             self.remove(nodeToRemove)\n",
    "             self.size = self.size-1\n",
    "         else:\n",
    "             raise KeyError('Error, key not in tree')\n",
    "      elif self.size == 1 and self.root.key == key:\n",
    "         self.root = None\n",
    "         self.size = self.size - 1\n",
    "      else:\n",
    "         raise KeyError('Error, key not in tree')\n",
    "\n",
    "    def __delitem__(self,key):\n",
    "       self.delete(key)\n",
    "\n",
    "    def spliceOut(self):\n",
    "       if self.isLeaf():\n",
    "           if self.isLeftChild():\n",
    "                  self.parent.leftChild = None\n",
    "           else:\n",
    "                  self.parent.rightChild = None\n",
    "       elif self.hasAnyChildren():\n",
    "           if self.hasLeftChild():\n",
    "                  if self.isLeftChild():\n",
    "                     self.parent.leftChild = self.leftChild\n",
    "                  else:\n",
    "                     self.parent.rightChild = self.leftChild\n",
    "                  self.leftChild.parent = self.parent\n",
    "           else:\n",
    "                  if self.isLeftChild():\n",
    "                     self.parent.leftChild = self.rightChild\n",
    "                  else:\n",
    "                     self.parent.rightChild = self.rightChild\n",
    "                  self.rightChild.parent = self.parent\n",
    "\n",
    "    def findSuccessor(self):\n",
    "      succ = None\n",
    "      if self.hasRightChild():\n",
    "          succ = self.rightChild.findMin()\n",
    "      else:\n",
    "          if self.parent:\n",
    "                 if self.isLeftChild():\n",
    "                     succ = self.parent\n",
    "                 else:\n",
    "                     self.parent.rightChild = None\n",
    "                     succ = self.parent.findSuccessor()\n",
    "                     self.parent.rightChild = self\n",
    "      return succ\n",
    "\n",
    "    def findMin(self):\n",
    "      current = self\n",
    "      while current.hasLeftChild():\n",
    "          current = current.leftChild\n",
    "      return current\n",
    "\n",
    "    def remove(self,currentNode):\n",
    "         if currentNode.isLeaf(): #leaf\n",
    "           if currentNode == currentNode.parent.leftChild:\n",
    "               currentNode.parent.leftChild = None\n",
    "           else:\n",
    "               currentNode.parent.rightChild = None\n",
    "         elif currentNode.hasBothChildren(): #interior\n",
    "           succ = currentNode.findSuccessor()\n",
    "           succ.spliceOut()\n",
    "           currentNode.key = succ.key\n",
    "           currentNode.payload = succ.payload\n",
    "\n",
    "         else: # this node has one child\n",
    "           if currentNode.hasLeftChild():\n",
    "             if currentNode.isLeftChild():\n",
    "                 currentNode.leftChild.parent = currentNode.parent\n",
    "                 currentNode.parent.leftChild = currentNode.leftChild\n",
    "             elif currentNode.isRightChild():\n",
    "                 currentNode.leftChild.parent = currentNode.parent\n",
    "                 currentNode.parent.rightChild = currentNode.leftChild\n",
    "             else:\n",
    "                 currentNode.replaceNodeData(currentNode.leftChild.key,\n",
    "                                    currentNode.leftChild.payload,\n",
    "                                    currentNode.leftChild.leftChild,\n",
    "                                    currentNode.leftChild.rightChild)\n",
    "           else:\n",
    "             if currentNode.isLeftChild():\n",
    "                 currentNode.rightChild.parent = currentNode.parent\n",
    "                 currentNode.parent.leftChild = currentNode.rightChild\n",
    "             elif currentNode.isRightChild():\n",
    "                 currentNode.rightChild.parent = currentNode.parent\n",
    "                 currentNode.parent.rightChild = currentNode.rightChild\n",
    "             else:\n",
    "                 currentNode.replaceNodeData(currentNode.rightChild.key,\n",
    "                                    currentNode.rightChild.payload,\n",
    "                                    currentNode.rightChild.leftChild,\n",
    "                                    currentNode.rightChild.rightChild)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "mytree = BinarySearchTree()\n",
    "mytree[3]=\"red\"\n",
    "mytree[4]=\"blue\"\n",
    "mytree[6]=\"yellow\"\n",
    "mytree[2]=\"at\"\n",
    "\n",
    "print(mytree[6])\n",
    "print(mytree[2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Balanced Binary Search Trees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A special kind of binary search tree that automatically makes sure that the tree remains balanced at all times. This tree is called an **AVL tree** and is named for its inventors: G.M. Adelson-Velskii and E.M. Landis."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An **AVL tree** implements the Map abstract data type just like a regular binary search tree, the only difference is in how the tree performs. To implement our **AVL tree** we need to keep track of a **balance factor** for each node in the tree. We do this by looking at the heights of the left and right subtrees for each node. More formally, we define the balance factor for a node as the difference between the height of the left subtree and the height of the right subtree.\n",
    "\n",
    "$$balanceFactor=height(leftSubTree)−height(rightSubTree)$$\n",
    "\n",
    "Using the definition for balance factor given above we say that a subtree is left-heavy if the balance factor is greater than zero. If the balance factor is less than zero then the subtree is right heavy. If the balance factor is zero then the tree is perfectly in balance. For purposes of implementing an **AVL tree**, and gaining the benefit of having a balanced tree we will define a tree to be in balance if the balance factor is -1, 0, or 1. Once the balance factor of a node in a tree is outside this range we will need to have a procedure to bring the tree back into balance. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def _put(self, key, val, currentNode):\n",
    "    if key < currentNode.key:\n",
    "        if currentNode.hasLeftChild():\n",
    "            self._put(key, val, currentNode.leftChild)\n",
    "        else:\n",
    "            currentNode.leftChild = TreeNode(key, val, parent=currentNode)\n",
    "            self.updateBalance(currentNode.leftChild)\n",
    "    else:\n",
    "        if currentNode.hasRightChild():\n",
    "            self._put(key, val, currentNode.rightChild)\n",
    "        else:\n",
    "            currentNode.rightChild = TreeNode(key, val, parent=currentNode)\n",
    "            self.updateBalance(currentNode.rightChild)\n",
    "\n",
    "\n",
    "def updateBalance(self, node):\n",
    "    if node.balanceFactor > 1 or node.balanceFactor < -1:\n",
    "        self.rebalance(node)\n",
    "        return\n",
    "    if node.parent != None:\n",
    "        if node.isLeftChild():\n",
    "            node.parent.balanceFactor += 1\n",
    "        elif node.isRightChild():\n",
    "            node.parent.balanceFactor -= 1\n",
    "\n",
    "        if node.parent.balanceFactor != 0:\n",
    "            self.updateBalance(node.parent)\n",
    "\n",
    "\n",
    "def rotateLeft(self, rotRoot):\n",
    "    newRoot = rotRoot.rightChild\n",
    "    rotRoot.rightChild = newRoot.leftChild\n",
    "    if newRoot.leftChild != None:\n",
    "        newRoot.leftChild.parent = rotRoot\n",
    "    newRoot.parent = rotRoot.parent\n",
    "    if rotRoot.isRoot():\n",
    "        self.root = newRoot\n",
    "    else:\n",
    "        if rotRoot.isLeftChild():\n",
    "            rotRoot.parent.leftChild = newRoot\n",
    "        else:\n",
    "            rotRoot.parent.rightChild = newRoot\n",
    "    newRoot.leftChild = rotRoot\n",
    "    rotRoot.parent = newRoot\n",
    "    rotRoot.balanceFactor = rotRoot.balanceFactor + \\\n",
    "        1 - min(newRoot.balanceFactor, 0)\n",
    "    newRoot.balanceFactor = newRoot.balanceFactor + \\\n",
    "        1 + max(rotRoot.balanceFactor, 0)\n",
    "\n",
    "\n",
    "def rebalance(self, node):\n",
    "    if node.balanceFactor < 0:\n",
    "        if node.rightChild.balanceFactor > 0:\n",
    "            self.rotateRight(node.rightChild)\n",
    "            self.rotateLeft(node)\n",
    "        else:\n",
    "            self.rotateLeft(node)\n",
    "    elif node.balanceFactor > 0:\n",
    "        if node.leftChild.balanceFactor < 0:\n",
    "            self.rotateLeft(node.leftChild)\n",
    "            self.rotateRight(node)\n",
    "        else:\n",
    "            self.rotateRight(node)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Summary of Map ADT Implementations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<table border=\"0\" class=\"table\" id=\"tab-compare\">\n",
    "<caption><strong>Table 1: Comparing the Performance of Different Map Implementations</strong></caption>\n",
    "<colgroup>\n",
    "<col width=\"13%\">\n",
    "<col width=\"27%\">\n",
    "<col width=\"14%\">\n",
    "<col width=\"22%\">\n",
    "<col width=\"24%\">\n",
    "</colgroup>\n",
    "<thead valign=\"bottom\">\n",
    "<tr class=\"row-odd\"><th class=\"head\">operation</th>\n",
    "<th class=\"head\">Sorted List</th>\n",
    "<th class=\"head\">Hash Table</th>\n",
    "<th class=\"head\">Binary Search Tree</th>\n",
    "<th class=\"head\">AVL Tree</th>\n",
    "</tr>\n",
    "</thead>\n",
    "<tbody valign=\"top\">\n",
    "<tr class=\"row-even\"><td>put</td>\n",
    "<td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-1-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-1\" style=\"width: 2.638em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 2.169em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.759em 1000.003em 3.106em -0.465em); top: -2.69em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-2\"><span class=\"mi\" id=\"MathJax-Span-3\" style=\"font-family: MathJax_Math; font-style: italic;\">O</span><span class=\"mo\" id=\"MathJax-Span-4\" style=\"font-family: MathJax_Main;\">(</span><span class=\"mi\" id=\"MathJax-Span-5\" style=\"font-family: MathJax_Math; font-style: italic;\">n</span><span class=\"mo\" id=\"MathJax-Span-6\" style=\"font-family: MathJax_Main;\">)</span></span><span style=\"display: inline-block; width: 0px; height: 2.696em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.361em; vertical-align: -0.354em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-1\">O(n)</script></span></td>\n",
    "<td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-2-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-7\" style=\"width: 2.52em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 2.052em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.759em 1000.003em 3.106em -0.465em); top: -2.69em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-8\"><span class=\"mi\" id=\"MathJax-Span-9\" style=\"font-family: MathJax_Math; font-style: italic;\">O</span><span class=\"mo\" id=\"MathJax-Span-10\" style=\"font-family: MathJax_Main;\">(</span><span class=\"mn\" id=\"MathJax-Span-11\" style=\"font-family: MathJax_Main;\">1</span><span class=\"mo\" id=\"MathJax-Span-12\" style=\"font-family: MathJax_Main;\">)</span></span><span style=\"display: inline-block; width: 0px; height: 2.696em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.361em; vertical-align: -0.354em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-2\">O(1)</script></span></td>\n",
    "<td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-3-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-13\" style=\"width: 2.638em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 2.169em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.759em 1000.003em 3.106em -0.465em); top: -2.69em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-14\"><span class=\"mi\" id=\"MathJax-Span-15\" style=\"font-family: MathJax_Math; font-style: italic;\">O</span><span class=\"mo\" id=\"MathJax-Span-16\" style=\"font-family: MathJax_Main;\">(</span><span class=\"mi\" id=\"MathJax-Span-17\" style=\"font-family: MathJax_Math; font-style: italic;\">n</span><span class=\"mo\" id=\"MathJax-Span-18\" style=\"font-family: MathJax_Main;\">)</span></span><span style=\"display: inline-block; width: 0px; height: 2.696em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.361em; vertical-align: -0.354em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-3\">O(n)</script></span></td>\n",
    "<td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-4-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-19\" style=\"width: 4.921em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 4.043em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.759em 1000.003em 3.106em -0.465em); top: -2.69em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-20\"><span class=\"mi\" id=\"MathJax-Span-21\" style=\"font-family: MathJax_Math; font-style: italic;\">O</span><span class=\"mo\" id=\"MathJax-Span-22\" style=\"font-family: MathJax_Main;\">(</span><span class=\"msubsup\" id=\"MathJax-Span-23\"><span style=\"display: inline-block; position: relative; width: 1.759em; height: 0px;\"><span style=\"position: absolute; clip: rect(1.818em 1000.003em 3.106em -0.524em); top: -2.69em; left: 0.003em;\"><span class=\"mi\" id=\"MathJax-Span-24\" style=\"font-family: MathJax_Main;\">log</span><span style=\"display: inline-block; width: 0px; height: 2.696em;\"></span></span><span style=\"position: absolute; top: -2.046em; left: 1.291em;\"><span class=\"mn\" id=\"MathJax-Span-25\" style=\"font-size: 70.7%; font-family: MathJax_Main;\">2</span><span style=\"display: inline-block; width: 0px; height: 2.286em;\"></span></span></span></span><span class=\"texatom\" id=\"MathJax-Span-26\" style=\"padding-left: 0.179em;\"><span class=\"mrow\" id=\"MathJax-Span-27\"><span class=\"mi\" id=\"MathJax-Span-28\" style=\"font-family: MathJax_Math; font-style: italic;\">n</span></span></span><span class=\"mo\" id=\"MathJax-Span-29\" style=\"font-family: MathJax_Main;\">)</span></span><span style=\"display: inline-block; width: 0px; height: 2.696em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.361em; vertical-align: -0.354em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-4\">O(\\log_2{n})</script></span></td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td>get</td>\n",
    "<td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-5-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-30\" style=\"width: 4.921em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 4.043em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.759em 1000.003em 3.106em -0.465em); top: -2.69em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-31\"><span class=\"mi\" id=\"MathJax-Span-32\" style=\"font-family: MathJax_Math; font-style: italic;\">O</span><span class=\"mo\" id=\"MathJax-Span-33\" style=\"font-family: MathJax_Main;\">(</span><span class=\"msubsup\" id=\"MathJax-Span-34\"><span style=\"display: inline-block; position: relative; width: 1.759em; height: 0px;\"><span style=\"position: absolute; clip: rect(1.818em 1000.003em 3.106em -0.524em); top: -2.69em; left: 0.003em;\"><span class=\"mi\" id=\"MathJax-Span-35\" style=\"font-family: MathJax_Main;\">log</span><span style=\"display: inline-block; width: 0px; height: 2.696em;\"></span></span><span style=\"position: absolute; top: -2.046em; left: 1.291em;\"><span class=\"mn\" id=\"MathJax-Span-36\" style=\"font-size: 70.7%; font-family: MathJax_Main;\">2</span><span style=\"display: inline-block; width: 0px; height: 2.286em;\"></span></span></span></span><span class=\"texatom\" id=\"MathJax-Span-37\" style=\"padding-left: 0.179em;\"><span class=\"mrow\" id=\"MathJax-Span-38\"><span class=\"mi\" id=\"MathJax-Span-39\" style=\"font-family: MathJax_Math; font-style: italic;\">n</span></span></span><span class=\"mo\" id=\"MathJax-Span-40\" style=\"font-family: MathJax_Main;\">)</span></span><span style=\"display: inline-block; width: 0px; height: 2.696em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.361em; vertical-align: -0.354em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-5\">O(\\log_2{n})</script></span></td>\n",
    "<td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-6-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-41\" style=\"width: 2.52em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 2.052em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.759em 1000.003em 3.106em -0.465em); top: -2.69em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-42\"><span class=\"mi\" id=\"MathJax-Span-43\" style=\"font-family: MathJax_Math; font-style: italic;\">O</span><span class=\"mo\" id=\"MathJax-Span-44\" style=\"font-family: MathJax_Main;\">(</span><span class=\"mn\" id=\"MathJax-Span-45\" style=\"font-family: MathJax_Main;\">1</span><span class=\"mo\" id=\"MathJax-Span-46\" style=\"font-family: MathJax_Main;\">)</span></span><span style=\"display: inline-block; width: 0px; height: 2.696em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.361em; vertical-align: -0.354em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-6\">O(1)</script></span></td>\n",
    "<td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-7-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-47\" style=\"width: 2.638em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 2.169em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.759em 1000.003em 3.106em -0.465em); top: -2.69em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-48\"><span class=\"mi\" id=\"MathJax-Span-49\" style=\"font-family: MathJax_Math; font-style: italic;\">O</span><span class=\"mo\" id=\"MathJax-Span-50\" style=\"font-family: MathJax_Main;\">(</span><span class=\"mi\" id=\"MathJax-Span-51\" style=\"font-family: MathJax_Math; font-style: italic;\">n</span><span class=\"mo\" id=\"MathJax-Span-52\" style=\"font-family: MathJax_Main;\">)</span></span><span style=\"display: inline-block; width: 0px; height: 2.696em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.361em; vertical-align: -0.354em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-7\">O(n)</script></span></td>\n",
    "<td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-8-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-53\" style=\"width: 4.921em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 4.043em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.759em 1000.003em 3.106em -0.465em); top: -2.69em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-54\"><span class=\"mi\" id=\"MathJax-Span-55\" style=\"font-family: MathJax_Math; font-style: italic;\">O</span><span class=\"mo\" id=\"MathJax-Span-56\" style=\"font-family: MathJax_Main;\">(</span><span class=\"msubsup\" id=\"MathJax-Span-57\"><span style=\"display: inline-block; position: relative; width: 1.759em; height: 0px;\"><span style=\"position: absolute; clip: rect(1.818em 1000.003em 3.106em -0.524em); top: -2.69em; left: 0.003em;\"><span class=\"mi\" id=\"MathJax-Span-58\" style=\"font-family: MathJax_Main;\">log</span><span style=\"display: inline-block; width: 0px; height: 2.696em;\"></span></span><span style=\"position: absolute; top: -2.046em; left: 1.291em;\"><span class=\"mn\" id=\"MathJax-Span-59\" style=\"font-size: 70.7%; font-family: MathJax_Main;\">2</span><span style=\"display: inline-block; width: 0px; height: 2.286em;\"></span></span></span></span><span class=\"texatom\" id=\"MathJax-Span-60\" style=\"padding-left: 0.179em;\"><span class=\"mrow\" id=\"MathJax-Span-61\"><span class=\"mi\" id=\"MathJax-Span-62\" style=\"font-family: MathJax_Math; font-style: italic;\">n</span></span></span><span class=\"mo\" id=\"MathJax-Span-63\" style=\"font-family: MathJax_Main;\">)</span></span><span style=\"display: inline-block; width: 0px; height: 2.696em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.361em; vertical-align: -0.354em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-8\">O(\\log_2{n})</script></span></td>\n",
    "</tr>\n",
    "<tr class=\"row-even\"><td>in</td>\n",
    "<td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-9-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-64\" style=\"width: 4.921em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 4.043em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.759em 1000.003em 3.106em -0.465em); top: -2.69em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-65\"><span class=\"mi\" id=\"MathJax-Span-66\" style=\"font-family: MathJax_Math; font-style: italic;\">O</span><span class=\"mo\" id=\"MathJax-Span-67\" style=\"font-family: MathJax_Main;\">(</span><span class=\"msubsup\" id=\"MathJax-Span-68\"><span style=\"display: inline-block; position: relative; width: 1.759em; height: 0px;\"><span style=\"position: absolute; clip: rect(1.818em 1000.003em 3.106em -0.524em); top: -2.69em; left: 0.003em;\"><span class=\"mi\" id=\"MathJax-Span-69\" style=\"font-family: MathJax_Main;\">log</span><span style=\"display: inline-block; width: 0px; height: 2.696em;\"></span></span><span style=\"position: absolute; top: -2.046em; left: 1.291em;\"><span class=\"mn\" id=\"MathJax-Span-70\" style=\"font-size: 70.7%; font-family: MathJax_Main;\">2</span><span style=\"display: inline-block; width: 0px; height: 2.286em;\"></span></span></span></span><span class=\"texatom\" id=\"MathJax-Span-71\" style=\"padding-left: 0.179em;\"><span class=\"mrow\" id=\"MathJax-Span-72\"><span class=\"mi\" id=\"MathJax-Span-73\" style=\"font-family: MathJax_Math; font-style: italic;\">n</span></span></span><span class=\"mo\" id=\"MathJax-Span-74\" style=\"font-family: MathJax_Main;\">)</span></span><span style=\"display: inline-block; width: 0px; height: 2.696em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.361em; vertical-align: -0.354em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-9\">O(\\log_2{n})</script></span></td>\n",
    "<td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-10-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-75\" style=\"width: 2.52em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 2.052em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.759em 1000.003em 3.106em -0.465em); top: -2.69em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-76\"><span class=\"mi\" id=\"MathJax-Span-77\" style=\"font-family: MathJax_Math; font-style: italic;\">O</span><span class=\"mo\" id=\"MathJax-Span-78\" style=\"font-family: MathJax_Main;\">(</span><span class=\"mn\" id=\"MathJax-Span-79\" style=\"font-family: MathJax_Main;\">1</span><span class=\"mo\" id=\"MathJax-Span-80\" style=\"font-family: MathJax_Main;\">)</span></span><span style=\"display: inline-block; width: 0px; height: 2.696em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.361em; vertical-align: -0.354em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-10\">O(1)</script></span></td>\n",
    "<td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-11-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-81\" style=\"width: 2.638em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 2.169em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.759em 1000.003em 3.106em -0.465em); top: -2.69em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-82\"><span class=\"mi\" id=\"MathJax-Span-83\" style=\"font-family: MathJax_Math; font-style: italic;\">O</span><span class=\"mo\" id=\"MathJax-Span-84\" style=\"font-family: MathJax_Main;\">(</span><span class=\"mi\" id=\"MathJax-Span-85\" style=\"font-family: MathJax_Math; font-style: italic;\">n</span><span class=\"mo\" id=\"MathJax-Span-86\" style=\"font-family: MathJax_Main;\">)</span></span><span style=\"display: inline-block; width: 0px; height: 2.696em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.361em; vertical-align: -0.354em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-11\">O(n)</script></span></td>\n",
    "<td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-12-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-87\" style=\"width: 4.921em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 4.043em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.759em 1000.003em 3.106em -0.465em); top: -2.69em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-88\"><span class=\"mi\" id=\"MathJax-Span-89\" style=\"font-family: MathJax_Math; font-style: italic;\">O</span><span class=\"mo\" id=\"MathJax-Span-90\" style=\"font-family: MathJax_Main;\">(</span><span class=\"msubsup\" id=\"MathJax-Span-91\"><span style=\"display: inline-block; position: relative; width: 1.759em; height: 0px;\"><span style=\"position: absolute; clip: rect(1.818em 1000.003em 3.106em -0.524em); top: -2.69em; left: 0.003em;\"><span class=\"mi\" id=\"MathJax-Span-92\" style=\"font-family: MathJax_Main;\">log</span><span style=\"display: inline-block; width: 0px; height: 2.696em;\"></span></span><span style=\"position: absolute; top: -2.046em; left: 1.291em;\"><span class=\"mn\" id=\"MathJax-Span-93\" style=\"font-size: 70.7%; font-family: MathJax_Main;\">2</span><span style=\"display: inline-block; width: 0px; height: 2.286em;\"></span></span></span></span><span class=\"texatom\" id=\"MathJax-Span-94\" style=\"padding-left: 0.179em;\"><span class=\"mrow\" id=\"MathJax-Span-95\"><span class=\"mi\" id=\"MathJax-Span-96\" style=\"font-family: MathJax_Math; font-style: italic;\">n</span></span></span><span class=\"mo\" id=\"MathJax-Span-97\" style=\"font-family: MathJax_Main;\">)</span></span><span style=\"display: inline-block; width: 0px; height: 2.696em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.361em; vertical-align: -0.354em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-12\">O(\\log_2{n})</script></span></td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td>del</td>\n",
    "<td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-13-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-98\" style=\"width: 3.106em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 2.52em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.759em 1000.003em 3.106em -0.465em); top: -2.69em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-99\"><span class=\"mi\" id=\"MathJax-Span-100\" style=\"font-family: MathJax_Math; font-style: italic;\">O</span><span class=\"mo\" id=\"MathJax-Span-101\" style=\"font-family: MathJax_Main;\">(</span><span class=\"mi\" id=\"MathJax-Span-102\" style=\"font-family: MathJax_Math; font-style: italic;\">n</span><span class=\"mo\" id=\"MathJax-Span-103\" style=\"font-family: MathJax_Main;\">)</span><span class=\"mo\" id=\"MathJax-Span-104\" style=\"font-family: MathJax_Main;\">)</span></span><span style=\"display: inline-block; width: 0px; height: 2.696em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.361em; vertical-align: -0.354em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-13\">O(n))</script></span></td>\n",
    "<td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-14-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-105\" style=\"width: 2.52em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 2.052em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.759em 1000.003em 3.106em -0.465em); top: -2.69em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-106\"><span class=\"mi\" id=\"MathJax-Span-107\" style=\"font-family: MathJax_Math; font-style: italic;\">O</span><span class=\"mo\" id=\"MathJax-Span-108\" style=\"font-family: MathJax_Main;\">(</span><span class=\"mn\" id=\"MathJax-Span-109\" style=\"font-family: MathJax_Main;\">1</span><span class=\"mo\" id=\"MathJax-Span-110\" style=\"font-family: MathJax_Main;\">)</span></span><span style=\"display: inline-block; width: 0px; height: 2.696em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.361em; vertical-align: -0.354em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-14\">O(1)</script></span></td>\n",
    "<td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-15-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-111\" style=\"width: 2.638em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 2.169em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.759em 1000.003em 3.106em -0.465em); top: -2.69em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-112\"><span class=\"mi\" id=\"MathJax-Span-113\" style=\"font-family: MathJax_Math; font-style: italic;\">O</span><span class=\"mo\" id=\"MathJax-Span-114\" style=\"font-family: MathJax_Main;\">(</span><span class=\"mi\" id=\"MathJax-Span-115\" style=\"font-family: MathJax_Math; font-style: italic;\">n</span><span class=\"mo\" id=\"MathJax-Span-116\" style=\"font-family: MathJax_Main;\">)</span></span><span style=\"display: inline-block; width: 0px; height: 2.696em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.361em; vertical-align: -0.354em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-15\">O(n)</script></span></td>\n",
    "<td><span class=\"math\"><span class=\"MathJax_Preview\"></span><span class=\"MathJax\" id=\"MathJax-Element-16-Frame\" role=\"textbox\" aria-readonly=\"true\"><nobr><span class=\"math\" id=\"MathJax-Span-117\" style=\"width: 4.921em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 4.043em; height: 0px; font-size: 122%;\"><span style=\"position: absolute; clip: rect(1.759em 1000.003em 3.106em -0.465em); top: -2.69em; left: 0.003em;\"><span class=\"mrow\" id=\"MathJax-Span-118\"><span class=\"mi\" id=\"MathJax-Span-119\" style=\"font-family: MathJax_Math; font-style: italic;\">O</span><span class=\"mo\" id=\"MathJax-Span-120\" style=\"font-family: MathJax_Main;\">(</span><span class=\"msubsup\" id=\"MathJax-Span-121\"><span style=\"display: inline-block; position: relative; width: 1.759em; height: 0px;\"><span style=\"position: absolute; clip: rect(1.818em 1000.003em 3.106em -0.524em); top: -2.69em; left: 0.003em;\"><span class=\"mi\" id=\"MathJax-Span-122\" style=\"font-family: MathJax_Main;\">log</span><span style=\"display: inline-block; width: 0px; height: 2.696em;\"></span></span><span style=\"position: absolute; top: -2.046em; left: 1.291em;\"><span class=\"mn\" id=\"MathJax-Span-123\" style=\"font-size: 70.7%; font-family: MathJax_Main;\">2</span><span style=\"display: inline-block; width: 0px; height: 2.286em;\"></span></span></span></span><span class=\"texatom\" id=\"MathJax-Span-124\" style=\"padding-left: 0.179em;\"><span class=\"mrow\" id=\"MathJax-Span-125\"><span class=\"mi\" id=\"MathJax-Span-126\" style=\"font-family: MathJax_Math; font-style: italic;\">n</span></span></span><span class=\"mo\" id=\"MathJax-Span-127\" style=\"font-family: MathJax_Main;\">)</span></span><span style=\"display: inline-block; width: 0px; height: 2.696em;\"></span></span></span><span style=\"border-left-width: 0.004em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.361em; vertical-align: -0.354em;\"></span></span></nobr></span><script type=\"math/tex\" id=\"MathJax-Element-16\">O(\\log_2{n})</script></span></td>\n",
    "</tr>\n",
    "</tbody>\n",
    "</table>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
